先求出有向圖強連通分量，縮點之后重新構圖，新圖為一個
有向無環圖，如果在這個DAG是只有一個出度為0的點，那么這個點所表示的強連通分量中的所有點都是符合要求的。
一開始使用list來構建鄰接表，結果TLE。后來改成用數組模擬，效率較高。
以下是我的代碼：
#include<stack>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(10007);
int n,m,n2,id[kMaxn];
int first[kMaxn],edge[5*kMaxn],next[5*kMaxn];
int dfscnt,dfsn[kMaxn],low[kMaxn];
stack<int> s;
void dfs(int u)
{
dfsn[u]=low[u]=++dfscnt;
s.push(u);
for(int i=first[u];i!=-1;i=next[i])
if(!dfsn[edge[i]])
{
dfs(edge[i]);
low[u]=min(low[u],low[edge[i]]);
}
else
low[u]=min(low[u],dfsn[edge[i]]);
if(dfsn[u]==low[u])
{
n2++;
int v;
do
{
v=s.top();s.pop();
id[v]=n2;
}while(v!=u);
}
}
bool Tarjan(int &num)
{
n2=dfscnt=0;
memset(dfsn,0,kMaxn*sizeof(int));
for(int i=1;i<=n;i++)
if(!dfsn[i])
dfs(i);
int counter(0),degree[kMaxn];
for(int i=1;i<=n2;i++)
degree[i]=0;
for(int u=1;u<=n;u++)
for(int i=first[u];i!=-1;i=next[i])
if(id[u]!=id[edge[i]])
degree[id[u]]++;
for(int i=1;i<=n2;i++)
if(!degree[i])
{
counter++;
num=i;
}
return (counter==1);
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
memset(first,-1,kMaxn*sizeof(int));
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
edge[i]=v;
next[i]=first[u];
first[u]=i;
}
int num;
if(Tarjan(num))
{
int ans(0);
for(int i=1;i<=n;i++)
if(id[i]==num)
ans++;
printf("%d\n",ans);
}
else
printf("%d\n",0);
}
return 0;
}
posted on 2011-06-02 16:35
lee1r 閱讀(143)
評論(0) 編輯 收藏 引用