Tarjan算法解读：https://www.byvoid.com/zht/blog/scc-tarjan
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<cstring> 5 #include<vector> 6 #include<stack> 7 #include<algorithm> 8 using namespace std; 9 10 #define N 10003 11 int dfn[N],low[N],ins[N],Time,num;//ins是否在栈里 12 vector<int>gra[N]; 13 stack<int>sta; 14 15 void Tarjan(int s) 16 { 17 dfn[s] = low[s] = ++Time; 18 sta.push(s); 19 ins[s] = 1; 20 for(int i=0;i<gra[s].size();i++) 21 { 22 int k = gra[s][i]; 23 if(dfn[k] == 0){ 24 Tarjan(k); 25 low[s] = min(low[s] ,low[k]); 26 } 27 if(dfn[k] != 0 && ins[k] == 1){ 28 low[s] = min(low[s] ,dfn[k]);//low[s] = min(low[s] ,low[k]);好像也是对的 29 } 30 } 31 if(dfn[s] == low[s]) 32 { 33 num++; 34 while(!sta.empty()) 35 { 36 int temp = sta.top(); 37 sta.pop(); 38 ins[temp] = 0; 39 if(temp == s) break; 40 } 41 } 42 } 43 44 int main() 45 { 46 int n,m; 47 while(scanf("%d%d",&n,&m)&&(n + m)) 48 { 49 memset(dfn,0,sizeof(dfn)); 50 memset(ins,0,sizeof(ins)); 51 memset(low,0,sizeof(low)); 52 while(!sta.empty()) sta.pop(); 53 for(int i=1;i<=n;i++) gra[i].clear(); 54 int a,b; 55 while(m--) 56 { 57 scanf("%d%d",&a,&b); 58 gra[a].push_back(b); 59 } 60 num = Time = 0; 61 for(int i=1;i<=n;i++) 62 { 63 if(dfn[i]==0) Tarjan(i); 64 } 65 if(num > 1) printf("No "); 66 else printf("Yes "); 67 } 68 }