首页 > 代码库 > POJ 2186

POJ 2186

2024-07-16 13:39:32   221人阅读

题目大意：

给定一系列A->B的关系,说明A崇拜B，若A崇拜B，B崇拜C，那么A崇拜C，问存在多少头牛被其他所有牛都崇拜

 

一道强连通分量的水题，将一个强连通分量的牛看做一个整体，记录每个强连通分量中牛的个数

其实我们仔细想想，当把所有强连通分量都缩点后，例如强连通分量为3，那么剩下来的有向边必然小于3，否则将会导致中间某处又生成环形成强连通分量

所以如果存在出度为0的连通分量2个及两个以上，说明这2点是不能互达的，说明没有牛被崇拜

同样道理，若只有一个，那么找到那个连通分量中牛的头数，这就是解

 

总代码如下：

 1 #include <cstdio> 2 #include <cstring> 3 #include <stack> 4 #include <algorithm> 5 using namespace std; 6 #define N 10005 7 struct Path{ 8     int y,next; 9 }path[50010];10 int tmpdfn,outdegree[N],cnt[N],scc[N],k,scc_cnt,first[N],dfn[N],low[N];11 stack<int> s;12 void add(int x,int y)13 {14     path[k].y=y,path[k].next=first[x];15     first[x]=k;16     k++;17 }18 void dfs(int u,int fa)19 {20     dfn[u]=low[u]=++tmpdfn;21     s.push(u);22     for(int i=first[u];i!=-1;i=path[i].next){23         int v=path[i].y;24         if(!dfn[v]){25             dfs(v,u);26             low[u]=min(low[v],low[u]);27         }28         else if(!scc[v]) low[u]=min(low[u],dfn[v]);29     }30     if(dfn[u]==low[u]){31         scc_cnt++;32         int m=0;33         for(;;){34             int t=s.top();s.pop();35             scc[t]=scc_cnt;36             m++;37             if(t==u) break;38         }39         cnt[scc_cnt]=m;40         //printf("scc: %d  %d\n",scc_cnt,m);41     }42 }43 void get_scc(int n)44 {45     for(int i=1;i<=n;i++)46         if(!dfn[i]) dfs(i,-1);47 48     for(int i=1;i<=n;i++)49         for(int j=first[i];j!=-1;j=path[j].next)50             if(scc[i]!=scc[path[j].y]){ outdegree[scc[i]]++;}51 }52 int main()53 {54     int n,m,a,b;55     scanf("%d%d",&n,&m);56     memset(dfn,0,sizeof(dfn));57     memset(first,-1,sizeof(first));58     memset(scc,0,sizeof(scc));59     memset(cnt,0,sizeof(cnt));60     memset(outdegree,0,sizeof(outdegree));61     tmpdfn=0,k=0,scc_cnt=0;62     for(int i=0;i<m;i++){63         scanf("%d%d",&a,&b);64         add(a,b);65     }66     get_scc(n);67     int t=0,p;68     for(int i=1;i<=scc_cnt;i++){69         //printf("%d\n",outdegree[i]);70         if(outdegree[i]==0) t++,p=i;71         if(t>=2) break;72     }73     if(t>=2) puts("0");74     else printf("%d\n",cnt[p]);75     return 0;76 }

 


联系
我们