题意：判断给定有向图中是否所有点都能够互相到达。
就是询问是否只有一个强连通分量。
1 #include<stdio.h>
2 #include<string.h>
3 #include<stack>
4 #include<queue>
5 using namespace std;
6
7 const int maxn=1e4+5;
8 const int maxm=1e5+5;
9
10 int head[maxn],point[maxm],nxt[maxm],size;
11 int n,t,scccnt;
12 int stx[maxn],low[maxn],scc[maxn];
13 stack<int>S;
14
15 void init(){
16 memset(head,-1,sizeof(head));
17 size=0;
18 }
19
20 void add(int a,int b){
21 point[size]=b;
22 nxt[size]=head[a];
23 head[a]=size++;
24 }
25
26 void dfs(int s){
27 stx[s]=low[s]=++t;
28 S.push(s);
29 for(int i=head[s];~i;i=nxt[i]){
30 int j=point[i];
31 if(!stx[j]){
32 dfs(j);
33 low[s]=min(low[s],low[j]);
34 }
35 else if(!scc[j]){
36 low[s]=min(low[s],stx[j]);
37 }
38 }
39 if(low[s]==stx[s]){
40 scccnt++;
41 while(1){
42 int u=S.top();S.pop();
43 scc[u]=scccnt;
44 if(s==u)break;
45 }
46 }
47 }
48
49 void setscc(){
50 memset(stx,0,sizeof(stx));
51 memset(scc,0,sizeof(scc));
52 t=scccnt=0;
53 for(int i=1;i<=n;++i)if(!stx[i])dfs(i);
54 }
55
56 int main(){
57 int m;
58 while(scanf("%d%d",&n,&m)!=EOF&&n+m){
59 init();
60 while(m--){
61 int a,b;
62 scanf("%d%d",&a,&b);
63 add(a,b);
64 }
65 setscc();
66 if(scccnt==1)printf("Yes
");
67 else printf("No
");
68 }
69 return 0;
70 }