這道題目就是求強連通分量。。。

這里采用的是Tarjan算法：http://m.blog.csdn.net/blog/qq574857122/16361033

AC代碼：

#include<iostream>v #include<cstdio> #include<cstring> using namespace std;const int maxn = 10005; struct Edge {int key,next; }edge[100000]; int pre[maxn],cnt,n,m,dfsNum,sccNum,top; int stack[maxn],instack[maxn],dfsnum[maxn],low[maxn];void addedge(int x,int y) {edge[cnt].key = y;edge[cnt].next = pre[x];pre[x] = cnt++; }void Tarjan(int cur) {dfsnum[cur] = ++dfsNum;low[cur] = dfsnum[cur];stack[top++] = cur;instack[cur] = 1;for(int i = pre[cur]; i != -1; i = edge[i].next){int v = edge[i].key;if(dfsnum[v] == 0) // 子樹中還有邊未遍歷{Tarjan(v);if(low[cur] > low[v])low[cur] = low[v];}else if(instack[v]) //表示有父子關系，存在回邊{if(low[cur] > dfsnum[v])low[cur] = dfsnum[v];}}if(low[cur] == dfsnum[cur]) //該點是強連通分量的根節(jié)點{while(top != 0 && stack[top-1] != cur){instack[stack[top-1]] = 0;top--;}sccNum++;} }int main() { while(scanf("%d%d",&n,&m)!=EOF && m + n){memset(pre,-1,sizeof(pre));memset(instack,0,sizeof(instack));cnt = top = sccNum = dfsNum = 0;for(int i = 1; i <= m; i++){int a,b;scanf("%d%d",&a,&b);addedge(a,b);}for(int i = 1; i <= n; i++)if(dfsnum[i] == 0)Tarjan(i);if(sccNum == 1)printf("Yes\n");else printf("No\n");}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1269（Tarjan求强连通分量）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。