首页 > 代码库 > POJ 3180 The Cow Prom(SCC)
POJ 3180 The Cow Prom(SCC)
【题目链接】 http://poj.org/problem?id=3180
【题目大意】
N头牛,M条有向绳子,能组成几个歌舞团?要求顺时针逆时针都能带动舞团内所有牛。
【题解】
等价于求点数大于1的SCC数量。
【代码】
#include <cstdio>#include <algorithm>#include <vector>#include <cstring> using namespace std;const int MAX_V=10000;int V; //顶点数vector<int> G[MAX_V]; //图的邻接表表示vector<int> rG[MAX_V]; //反向图vector<int> vs; //后序遍历bool used[MAX_V];int cmp[MAX_V]; //所属强连通分量的拓扑序void add_edge(int from,int to){ G[from].push_back(to); rG[to].push_back(from);} void dfs(int v){ used[v]=1; for(int i=0;i<G[v].size();i++){ if(!used[G[v][i]])dfs(G[v][i]); }vs.push_back(v);}void rdfs(int v,int k){ used[v]=1; cmp[v]=k; for(int i=0;i<rG[v].size();i++){ if(!used[rG[v][i]])rdfs(rG[v][i],k); }}int scc(){ memset(used,0,sizeof(used)); vs.clear(); for(int v=0;v<V;v++){if(!used[v])dfs(v);} memset(used,0,sizeof(used)); int k=0; for(int i=vs.size()-1;i>=0;i--){ if(!used[vs[i]])rdfs(vs[i],k++); }return k;}const int MAX_M=50000;int N,M;int A[MAX_M],B[MAX_M];int cnt[MAX_M];void solve(){ V=N; for(int i=0;i<M;i++){ add_edge(A[i]-1,B[i]-1); }int n=scc(); int num=0; memset(cnt,0,sizeof(cnt)); for(int i=0;i<V;i++)++cnt[cmp[i]]; for(int i=0;i<n;i++)if(cnt[i]>1)num++; printf("%d\n",num);}int main(){ while(~scanf("%d%d",&N,&M)){ for(int i=0;i<M;i++)scanf("%d%d",&A[i],&B[i]); solve(); }return 0;}
POJ 3180 The Cow Prom(SCC)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。