C - Don’t be cycle
https://atcoder.jp/contests/abc288/tasks/abc288_c
思路
检测出最小环有几个,
然后破掉相同数目的边即可。
检测最小环数目方法:
Code
https://atcoder.jp/contests/abc288/submissions/38629260
链式前向星
https://zhuanlan.zhihu.com/p/343092172
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6; struct node{ int to,next; }e[maxn]; int cnt; int nums = 0; int head[maxn],vis[maxn]; void addnode(int u,int v){ e[++cnt].to = v; e[cnt].next = head[u]; head[u] = cnt; } void dfs(int x, int fa){ vis[x] = 1; for(int i = head[x]; i; i=e[i].next){ int y = e[i].to; if(y==fa) { continue; } if(vis[y]==0){ dfs(y,x); } else if(vis[y]==1){ nums++; } else if(vis[y]==2){ // 2 status means already cycle counted, so do count again } } vis[x] = 2; } int main() { int n,m; int u,v; cin >> n >> m; for(int i = 1;i <= m;i++){ cin >> u >> v; addnode(u,v); addnode(v,u); } for(int i = 1;i <= n;i++){ if(vis[i]==0){ dfs(i,-1); } } cout << nums << endl; return 0; }
另外一种思路: 使用拓扑排序,删除环外元素, 然后使用并查集统计环的个数。
https://zhuanlan.zhihu.com/p/352710315
原文链接: https://www.cnblogs.com/lightsong/p/17092737.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/316187
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!