判斷一個有向圖是否強連通。
以下是我的代碼：
#include<list>
#include<stack>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(10007);
int n,m,n2,id[kMaxn];
list<int> g[kMaxn];
int dfscnt,dfsn[kMaxn],low[kMaxn];
stack<int> s;
void dfs(int u)
{
dfsn[u]=low[u]=++dfscnt;
s.push(u);
for(list<int>::iterator i=g[u].begin();i!=g[u].end();i++)
{
int v(*i);
if(!dfsn[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else
low[u]=min(low[u],dfsn[v]);
}
if(dfsn[u]==low[u])
{
n2++;
int v;
do
{
v=s.top();s.pop();
id[v]=n2;
}while(v!=u);
}
}
void Tarjan()
{
n2=dfscnt=0;
memset(dfsn,0,kMaxn*sizeof(int));
for(int i=1;i<=n;i++)
if(!dfsn[i])
dfs(i);
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(scanf("%d%d",&n,&m)==2 && (n || m))
{
for(int i=1;i<=n;i++)
g[i].clear();
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
}
Tarjan();
if(n2==1)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
posted on 2011-06-02 15:25
lee1r 閱讀(456)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論