hdu2767 Proving Equivalences,有向图强联通,Kosaraju算法
算法 联通 有向图
2023-09-14 09:09:00 时间
有向图强联通,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; }
相关文章
- 算法知识之最长公共子序列问题(动态规划)
- Java实现 蓝桥杯VIP 算法提高 陶陶摘苹果2
- Java实现 蓝桥杯 算法提高 拿糖果
- 谱聚类算法及其代码(Spectral Clustering)
- 实现一个简单的虚拟demo算法
- ML:从0到1 机器学习算法思路实现全部过程最强攻略
- 【智能算法】朴素贝叶斯算法实现
- 必知必会,这4种算法超参自动优化方法真香啊
- m基于OFDM系统,对比SC算法,Minn算法,PARK算法同步性能matlab仿真分析
- 【深度强化学习】Actor-Critic算法
- Batch Normalization的算法本质是在网络每一层的输入前增加一层BN层(也即归一化层),对数据进行归一化处理,然后再进入网络下一层,但是BN并不是简单的对数据进行求归一化,而是引入了两个参数λ和β去进行数据重构
- 图像算法所用软件下载汇总