codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include<iostream> #include<cstdio> #include<cstdlib> #include<ctime> #include<utility> #include<algorithm> #include<vector> #include<queue> #include<set> #include<map> #include<cmath> #include<cstring> #include<cctype> using namespace std; int n,m; vector<int> g[10005],rg[10005],vs; int k; bool used[10005]; int cmp[10005]; int u,num; void init() { memset(g,0,sizeof(g)); memset(rg,0,sizeof(rg)); k=0; u=0;num=0; } void dfs(int i) { used[i]=true; for(int j=0;j<g[i].size();j++) if(!used[g[i][j]]) dfs(g[i][j]); vs.push_back(i); } void rdfs(int i,int x) { used[i]=true; cmp[i]=x; for(int j=0;j<rg[i].size();j++) if(!used[rg[i][j]]) rdfs(rg[i][j],x); } int scc() { memset(used,false,sizeof(used)); vs.clear();//* for(int i=1;i<=n;i++) if(!used[i]) dfs(i); memset(used,false,sizeof(used)); int p=0; for(int i=vs.size()-1;i>=0;i--) if(!used[vs[i]]) rdfs(vs[i],++p); return p; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { init(); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); rg[y].push_back(x); } k=scc(); for(int i=1;i<=n;i++) { if(cmp[i]==k) { u=i; num++; } } memset(used,false,sizeof(used)); rdfs(u,0); for(int i=1;i<=n;i++) if(!used[i]) { num=0; break; } printf("%d\n",num); } return 0; }
Private
[
?
]
Run code
Submit