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; }
标签:cnt,Don,int,head,vis,maxn,cycle From: https://www.cnblogs.com/lightsong/p/17092737.html