为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。
3 3 1 2 2 3 3 1 3 3 1 2 2 3 3 2 0 0
Yes No
思路：
若强连通分量为不为1，说明不是所有点都是互相可达的。
#include<iostream>
#include<stack>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx = 1e4 + 5;
struct aa{int to, next;
}edge[10 * mx];
int head[mx], vis_stack[mx], low[mx], dfn[mx];
int n, m, cnt, jud, num;
stack<int> st;void add(int u, int v){edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++;
}
void tarjan(int x){dfn[x] = low[x] = ++num;vis_stack[x] = 1; //智障标记成0 st.push(x);int to;for(int i = head[x]; i != -1; i = edge[i].next){to = edge[i].to;if(dfn[to] == -1){tarjan(to);low[x] = min(low[x], low[to]);} else{if(vis_stack[to]) low[x] = dfn[to];}}int te;if(dfn[x] == low[x]){jud++;te = st.top();st.pop();vis_stack[te] = 0; //忘了标记 while(te != x){te = st.top();st.pop();vis_stack[te] = 0;} }
}
void init(){memset(head, -1, sizeof(head));memset(vis_stack, 0, sizeof(vis_stack));memset(low, 0, sizeof(low));memset(dfn, -1, sizeof(dfn));while(!st.empty()) st.pop() ; cnt = 0;jud = 0;num = 0;
}
int main(){while(scanf("%d%d", &n, &m)&&(n || m)){init();int a, b;while(m--){scanf("%d%d", &a, &b);add(a, b);}for(int i = 1; i <= n; i++)if(dfn[i] == -1) tarjan(i);if(jud == 1) puts("Yes");else puts("No");// cout<<jud<<endl; }return 0;
}