首页 > 代码库 > hdu 2767Proving Equivalences(强连通分量压缩 )
hdu 2767Proving Equivalences(强连通分量压缩 )
强连通分量压缩是
先缩点,然后计算各个强连通分量的入度为0的个数,出度为0的个数求他们最大值
#include <stdio.h> #include <string.h> #include <vector> #include <stack> #include <algorithm> using namespace std; #define N 20005 stack<int>sta; vector<int>mp[N]; int dfn[N]; int low[N]; int InStack[N]; int indexx,number; int n, m; int id[N]; void tarjan(int u) { InStack[u] = 1; low[u] = dfn[u] = ++ indexx; sta.push(u); for (int i = 0; i < mp[u].size(); ++ i) { int t = mp[u][i]; if (dfn[t] == 0) { tarjan(t); low[u] = min(low[u], low[t]); } else if (InStack[t] == 1) { low[u] = min(low[u], dfn[t]); } } if (low[u] == dfn[u]) { ++ number; while (!sta.empty()) { int v = sta.top(); sta.pop(); id[v]=number; InStack[v] = 0; if (v == u) break; } } } int main() { //freopen("input.txt","r",stdin); int T; while(scanf("%d",&T)==1) { while(T--) { scanf("%d%d",&n,&m); memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(InStack, 0, sizeof(InStack)); indexx = number = 0; for (int i = 1; i <= n; ++ i) { mp[i].clear(); } while(!sta.empty()) sta.pop(); for(int i=1; i<=m; i++) { int a,b; scanf("%d%d",&a,&b); mp[a].push_back(b); } for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i); if(number==1) { printf("0\n"); continue; } memset(dfn, 0, sizeof( dfn)); memset(low, 0, sizeof (low)); for(int i=1; i<=n; i++)//计算出入度 { for(int j=0; j<mp[i].size(); j++) { if(id[i]!=id[mp[i][j]]) dfn[id[i]]++, low[id[mp[i][j]]]++;//如果他们不在同一个的强连通分量话,把id【i】的出度++,id【他的节点】所在的连通分量的入度加加 } } /*for(int i=1; i<=number; i++){ printf("%d %d\n",dfn[i],low[i]); }*/ int ans1=0, ans2=0; for(int i=1; i<=number; i++) { if(dfn[i]==0) ans1++; if(low[i]==0) ans2++; } printf("%d\n", max(ans1, ans2)); } } }
hdu 2767Proving Equivalences(强连通分量压缩 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。