Tarjan真NB,强连通分量,割点,桥,点双连通分量,边双连通分量,LCA都有Tarjan的身影,这么多东西还有很多不懂的地方...
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<stack> #include<fstream> using namespace std; #define maxv 10005 vector<int> E[maxv],V[maxv],NE[maxv]; stack<int> Stack; int DFN[maxv],LOW[maxv]; bool Instack[maxv]; int Index,Cnt,Out[maxv],Belong[maxv]; void Init_Tarjan() { int i; for(i=1;i<=maxv;++i) V[i].clear(),NE[maxv].clear(); while(!Stack.empty()) Stack.pop(); memset(DFN,0,sizeof(DFN)); memset(LOW,0,sizeof(LOW)); memset(Instack,false,sizeof(Instack)); Cnt=Index=0; memset(Out,0,sizeof(Out)); } void Tarjan(int u) { DFN[u]=LOW[u]=++Index; Stack.push(u); Instack[u]=true; int v,i; for(i=0;i<E[u].size();++i) { v=E[u][i]; if(DFN[v]==0) { Tarjan(v); LOW[u]=min(LOW[u],LOW[v]); } else if(Instack[v]) LOW[u]=min(LOW[u],DFN[v]); } if(DFN[u]==LOW[u]) { Cnt++; do{ v=Stack.top(); Stack.pop(); Instack[v]=false; V[Cnt].push_back(v); Belong[v]=Cnt; }while(v!=u); } } int Create_New_Graph() { int i,j,k,v,cnt,ans; bool in[maxv]; for(i=1;i<=Cnt;++i) { memset(in,false,sizeof(in)); for(j=0;j<V[i].size();++j) { for(k=0;k<E[V[i][j]].size();++k) { v=E[V[i][j]][k]; in[Belong[v]]=true; } } in[i]=false; cnt=0; for(j=1;j<=Cnt;++j) if(in[j]==true) cnt++; Out[i]=cnt; } cnt=0; for(i=1;i<=Cnt;++i) if(Out[i]==0) cnt++,ans=i; if(cnt==1) return ans; else return -1; } int main() { int n,m,i,fm,to,ans; while(cin>>n>>m) { for(i=1;i<=n;++i) E[i].clear(); for(i=1;i<=m;++i) { cin>>fm>>to; E[fm].push_back(to); } Init_Tarjan(); for(i=1;i<=n;++i) if(DFN[i]==0) Tarjan(i); ans=Create_New_Graph(); if(ans==-1) cout<<0<<endl; else cout<<V[ans].size()<<endl; } return 0; }