Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 27698 | Accepted: 11148 |
Description
Input
Output
Sample Input
3 3 1 2 2 1 2 3
Sample Output
1
Hint
#include<stdio.h> #include<string.h> #include<algorithm> #include<vector> #include<stack> #define MAX 50010 #define INF 0x3f3f3f using namespace std; struct node { int beg,end,next; }edge[MAX]; int low[MAX],dfn[MAX]; int n,m,ans; int sccno[MAX],instack[MAX]; int dfsclock,scccnt; vector<int>newmap[MAX]; vector<int>scc[MAX]; int head[MAX]; int out[MAX]; stack<int>s; int sum,sumout,ant; void init() { ans=0; memset(head,-1,sizeof(head)); } void add(int u,int v) { edge[ans].beg=u; edge[ans].end=v; edge[ans].next=head[u]; head[u]=ans++; } void getmap() { int a,b,i; while(m--) { scanf("%d%d",&a,&b); add(a,b); } } void tarjan(int u) { int v,i,j; s.push(u); instack[u]=1; dfn[u]=low[u]=++dfsclock; for(i=head[u];i!=-1;i=edge[i].next) { v=edge[i].end; if(!dfn[v]) { 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]) { scccnt++; while(1) { v=s.top(); s.pop(); instack[v]=0; sccno[v]=scccnt; if(v==u) break; } } } void find(int l,int r) { memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(instack,0,sizeof(instack)); memset(sccno,0,sizeof(sccno)); dfsclock=scccnt=0; for(int i=l;i<=r;i++) { if(!dfn[i]) tarjan(i); } } void suodian() { int i; ant=0; for(i=1;i<=scccnt;i++) { newmap[i].clear(); out[i]=0; } for(i=0;i<ans;i++) { int u=sccno[edge[i].beg]; int v=sccno[edge[i].end]; if(u!=v) { newmap[u].push_back(v); out[u]++; } } } void solve() { int i,j; sumout=0;sum=0; for(i=1;i<=scccnt;i++) { if(!out[i]) { sumout++; ant=i; } } if(sumout==0) { printf("%d\n",n); return ; } else if(sumout==1) { for(i=1;i<=n;i++) if(sccno[i]==ant) sum++; printf("%d\n",sum); } else printf("0\n"); } int main() { int t; while(scanf("%d%d",&n,&m)!=EOF) { init(); getmap(); find(1,n); suodian(); solve(); } return 0; }
poj 2186 Popular Cows【tarjan求scc个数&&缩点】【求一个图中可以到达其余所有任意点的点的个数】
原文:http://www.cnblogs.com/tonghao/p/4823588.html