61.187.179.132:8080/JudgeOnline/showproblem
额。。这是很老的强联通题目了。刚刚弄懂了Tarjan算法。。就像实践一下。。结果WA了
很久。。最后发现原来是Stack搞错了。。真是悲剧。。
就是求出每个强联通分量，然后如果入度为0的分量只有一个，答案就是这个分量的大小，否则就是0
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=10000;
vector<int> E[maxn];
typedef vector<int>::iterator it;
int ord[maxn],low[maxn],cnt=0,id[maxn],snt=0,n,m;
bool inStack[maxn]={0};
stack<int> Stack;
void dfs(int x)
{
ord[x]=low[x]=cnt++;
inStack[x]=true;Stack.push(x);
for(it i=E[x].begin();i!=E[x].end();++i)
{
if(ord[*i]==-1)
dfs(*i),low[x]=min(low[x],low[*i]);
else if(inStack[*i]) low[x]=min(low[x],ord[*i]);
}
if(ord[x]==low[x])
{
int u;do{u=Stack.top();Stack.pop();id[u]=snt;inStack[u]=false;}while(u!=x);
snt++;
}
}
int Num[maxn]={0},In[maxn]={0};
int main()
{
//freopen("in","r",stdin);
cin>>n>>m;int s,t;
while(m–) scanf("%d %d",&s,&t),E[t-1].pb(s-1);
rep(i,n) ord[i]=-1;
rep(i,n)if(ord[i]==-1) dfs(i);
rep(i,n){
int own=id[i];for(it e=E[i].begin();e!=E[i].end();++e)if(id[*e]!=own) In[id[*e]]++;
Num[own]++;
}
t=0;int ans=0;rep(i,snt)if(In[i]==0) ++t,ans+=Num[i];
if(t>1)cout<<0<<endl;
else cout<<ans<<endl;
}