首页 > 代码库 > POJ 2186 Popular cows(Kosaraju+强联通分量模板）
POJ 2186 Popular cows(Kosaraju+强联通分量模板）
题目链接：http://poj.org/problem?id=2186
题目大意：给定N头牛和M个有序对(A,B),(A,B)表示A牛认为B牛是红人，该关系具有传递性，如果牛A认为牛B是红人，牛B认为牛C是红人，那么牛A也认为牛C是红人。求被其他所有牛认为是红牛的牛的总数。
解题思路：把所有牛看成顶点，把有序对（A,B）看成从A到B的有向边，那么题目就变成了求所有顶点都可到达的顶点的总数。我们可以得到一个结论，如果一个强连通分量里有一头牛被认为是红人，那么该强联通分量里的所有牛都是红人，这显然是正确的。由于我用的是Kosaraju求强联通分量，根据该算法性质，红牛只会在拓扑序最后的强联通分量里，我只需要找到最后一块强联通分量，取其中一个顶点，看是否所有点都可以到达即可。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 using namespace std; 6 const int N=1e4+5; 7 8 vector<int>G[N];//图的邻接表 9 vector<int>rG[N];//反向图的邻接表 10 vector<int>vs;//后序遍历的顺序的顶点列表 11 bool used[N];//记录点是否被访问 12 int cmp[N];//cmp[i]表示点i所属强联通分量的拓扑序 13 14 int V,E;15 16 void addedge(int u,int v){17 G[u].push_back(v);18 rG[v].push_back(u);19 } 20 21 void dfs(int v){22 used[v]=true;23 for(int i=0;i<G[v].size();i++){24 if(!used[G[v][i]])25 dfs(G[v][i]);26 }27 //回溯前进行标号 28 vs.push_back(v);29 }30 31 void rdfs(int v,int k){32 used[v]=true;33 //点v属于第k个强连通分量 34 cmp[v]=k;35 for(int i=0;i<rG[v].size();i++){36 if(!used[rG[v][i]])37 rdfs(rG[v][i],k);38 }39 }40 41 int scc(){42 memset(used,false,sizeof(used));43 vs.clear();44 //第一次DFS 45 for(int i=1;i<=V;i++){46 if(!used[i])47 dfs(i);48 }49 memset(used,false,sizeof(used));50 int k=0;//强联通分量块数 51 //第二次DFS52 for(int i=vs.size()-1;i>=0;i--){53 if(!used[vs[i]]) 54 rdfs(vs[i],++k);55 }56 return k;57 }58 59 void solve(){60 //获得强联通块数 61 int n=scc();62 //统计备选解的个数 63 int u=0,num=0;64 for(int i=1;i<=V;i++){65 if(cmp[i]==n){66 u=i;67 num++;68 }69 }70 //检查是否所有点可达71 memset(used,0,sizeof(used));72 rdfs(u,0);73 74 for(int i=1;i<=V;i++){75 if(!used[i]){76 num=0;77 break;78 }79 }80 for(int i=1;i<=V;i++){81 cout<<"i="<<i<<" cmp="<<cmp[i]<<endl;82 }83 printf("%d\n",num);84 }85 86 int main(){87 scanf("%d%d",&V,&E);88 for(int i=1;i<=E;i++){89 int u,v;90 scanf("%d%d",&u,&v);91 addedge(u,v);92 }93 solve();94 return 0; 95 }
POJ 2186 Popular cows(Kosaraju+强联通分量模板）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。