先求出有向图强连通分量，缩点之后重新构图，新图为一个
有向无环图，如果在这个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 阅读(128)
评论(0) 编辑 收藏 引用