双DFS方法就是正dfs扫一遍，然后将边反向dfs扫一遍。《挑战程序设计》上有说明。
双dfs代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector> using namespace std;
const int MAXN = 1e4 + ;
vector <int> G[MAXN]; //图的邻接表
vector <int> RG[MAXN]; //图的反向邻接表
vector <int> vs; //后序遍历的顶点顺序表
bool ok[MAXN]; //访问标记
int node[MAXN]; //所属强连通分量的序号
//第一次dfs
void dfs(int u) {
ok[u] = true;
for(int i = ; i < G[u].size() ; i++) {
if(!ok[G[u][i]])
dfs(G[u][i]);
}
vs.push_back(u);
}
//第二次dfs
void rdfs(int u , int k) {
node[u] = k;
ok[u] = true;
for(int i = ; i < RG[u].size() ; i++) {
if(!ok[RG[u][i]])
rdfs(RG[u][i] , k);
}
} int main()
{
int n , m , u , v;
while(~scanf("%d %d" , &n , &m) && (n || m)) {
for(int i = ; i <= n ; i++) {
G[i].clear();
RG[i].clear();
ok[i] = false;
vs.clear();
}
for(int i = ; i < m ; i++) {
scanf("%d %d" , &u , &v);
G[u].push_back(v);
RG[v].push_back(u);
}
//第一次dfs 选取任意的顶点作为起点遍历 后序遍历 越接近图尾部(叶子)的顶点顺序越小
for(int i = ; i <= n ; i++) {
if(!ok[i])
dfs(i);
}
memset(ok , false , sizeof(ok));
int k = ;
//第二次dfs 将边反向遍历 以标记最大的顶点作为起点遍历 这样便可以给强连通分量标号
for(int i = vs.size() - ; i >= ; i--) {
if(!ok[vs[i]])
rdfs(vs[i] , ++k);
}
if(k > ) {
printf("No\n");
}
else {
printf("Yes\n");
}
}
}
tarjan代码虽然比双dfs多，理解也稍微复杂，但是用处比较多，像求LCA 桥 scc之类的问题。
推荐一个学scc的blog，讲的很好。 https://www.byvoid.com/blog/tag/%E5%9C%96%E8%AB%96
代码如下：
//以hdu1269为例
//强连通分量 tarjan算法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 1e4 + ;
vector <int> G[MAXN]; //临接表
bool instack[MAXN]; //i是否还在在栈里
int sccnum , index; //连通分量数 和时间顺序
int top , st[MAXN]; //存储i的模拟栈
int block[MAXN]; //i所属的连通分量
int low[MAXN] , dfn[MAXN]; //i能最早访问到的点 和时间戳 void tarjan(int u) {
st[++top] = u;
instack[u] = true;
low[u] = dfn[u] = ++index;
for(int i = ; i < G[u].size() ; i++) {
int v = G[u][i];
if(!dfn[v]) { //v点没访问过
tarjan(v);
if(low[v] < low[u]) { //回溯上来 low[v]表示的时间戳(连通分量的根) u和v在一个连通分量里
low[u] = low[v];
}
}
else if(instack[v]) { //v还在栈里 说明u和v在一个连通分量(形成环路) v相当于连通分量的一个根
low[u] = min(low[u] , dfn[v]);
}
}
int v;
if(dfn[u] == low[u]) { //是连通分量的根
sccnum++;
do {
v = st[top--];
block[v] = sccnum;
instack[v] = false;
}while(v != u); //连通分量的所有的点
}
} void init(int n) {
for(int i = ; i <= n ; i++) {
G[i].clear();
instack[i] = false;
dfn[i] = ;
}
sccnum = index = top = ;
} int main()
{
int n , m , u , v;
while(~scanf("%d %d" , &n , &m) && (n || m)) {
init(n);
for(int i = ; i < m ; i++) {
scanf("%d %d" , &u , &v);
G[u].push_back(v);
}
for(int i = ; i <= n ; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
if(sccnum > ) {
cout << "No\n";
}
else {
cout << "Yes\n";
}
}
}