题意：给定有向图，判断是否为强连通图。
思路：方法很简单，直接Tarjan求图强连通分量个数是否为一即可。主要是把Tarjan模板附上来以后好整理。。。
Byvoid的Tarjan算法讲解很详细：https://www.byvoid.com/blog/scc-tarjan/
#include#include #include #include #define NODENUM 10005 #define EDGENUM 100005 using namespace std; int N,M; struct edgenode { int to,next; }Edge[EDGENUM]; int head[NODENUM],edgenum; bool in[NODENUM]; stack S; int rn,dfn[NODENUM],low[NODENUM],index; void init() { memset(head,-1,sizeof(head)); memset(in,0,sizeof(in)); memset(dfn,0,sizeof(dfn)); index=rn=edgenum=0; while(!S.empty()) S.pop(); } void add(int a,int b) { ++edgenum; Edge[edgenum].next = head[a]; Edge[edgenum].to = b; head[a] = edgenum; } void build() { while(M--) { int a,b; scanf("%d %d",&a,&b); add(a,b); } } void tarjan(int u) { dfn[u] = low[u] = ++index; S.push(u); in[u]=1; for(int p=head[u];~p;p = Edge[p].next) { int i = Edge[p].to; if(!dfn[i]) { tarjan(i); low[u] = min(low[u],low[i]); } else if(in[i]) low[u] = min(low[u],low[i]); } if(dfn[u] == low[u]) { ++rn; int v; do { v = S.top(); S.pop(); in[v]=0; } while(u!=v); } } void work() { for(int i=1;i<=N;++i) if(!dfn[i]) tarjan(i); printf("%s\n",rn == 1 "Yes":"No"); } int main() { while(~scanf("%d %d",&N,&M) && N+M) { init(); build(); work(); } return 0; }