首页 > 代码库 > hdu2767 Proving Equivalences,有向图强联通,Kosaraju算法
hdu2767 Proving Equivalences,有向图强联通,Kosaraju算法
点击打开链接
有向图强联通,Kosaraju算法
缩点后分别入度和出度为0的点的个数 answer = max(a, b);
scc_cnt = 1; answer = 0
#include<cstdio> #include<algorithm> #include<vector> #include<cstring> #include<stack> using namespace std; const int maxn = 20000 + 10; vector<int> G[maxn], G2[maxn]; vector<int> S; int vis[maxn], sccno[maxn], scc_cnt; void dfs1(int u){ if(vis[u]) return ; vis[u] = 1; for(int i=0; i<G[u].size(); ++i) dfs1(G[u][i]); S.push_back(u); } void dfs2(int u){ if(sccno[u]) return ; sccno[u] = scc_cnt; for(int i=0; i<G2[u].size(); ++i)dfs2(G2[u][i]); } void find_scc(int n){ scc_cnt = 0; S.clear(); memset(sccno, 0, sizeof sccno ); memset(vis, 0, sizeof vis ); for(int i=0; i<n; ++i) dfs1(i); for(int i=n-1; i>=0; --i){ if(!sccno[S[i]]) { scc_cnt++; dfs2(S[i]); } } } int in[maxn], out[maxn]; int main(){ int T, n, m; scanf("%d", &T); while(T--){ scanf("%d%d", &n, &m); for(int i=0; i<n; ++i) { G[i].clear(); G2[i].clear(); } for(int i=0; i<m; ++i){ int u, v; scanf("%d%d", &u, &v); u--; v--; G[u].push_back(v); G2[v].push_back(u); } find_scc(n); if(scc_cnt==1){ printf("0\n"); continue; } memset(in, 0, sizeof in ); memset(out, 0, sizeof out ); for(int u=0; u<n; ++u){ for(int i=0; i<G[u].size(); ++i){ int &v = G[u][i]; if(sccno[u] != sccno[v]) { out[sccno[u]]++; in[sccno[v]]++; } } } int a = 0, b = 0; for(int i=1; i<=scc_cnt; ++i){ if(!in[i]) a++; if(!out[i]) b++; } printf("%d\n", max(a, b)); } return 0; }
hdu2767 Proving Equivalences,有向图强联通,Kosaraju算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。