当前位置: 代码迷 >> 综合 >> Cyclic Components (深搜)
  详细解决方案

Cyclic Components (深搜)

热度:90   发布时间:2023-12-26 13:22:04.0

题目链接:传送门

题意: 给出一些无向图,问有多少个“纯粹”的单环,纯粹的环就是环中每个点只有两个邻接点

思路环中每个点只有两个邻接点 , 从这个点去突破问题,以每个点为起点去深搜,如果遍历这个点的邻接点,所有的邻接点(包括自身)如果都只有两个临界点,这就是一个纯粹的环,把所有遍历过的点标记,以后就不要再用这些点为起点去深搜,因为如果用这些点搜得的情况是重复的。

参考代码:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;const int N = 200010;
vector <int> a[N];
bool vis[N], flag;void dfs(int i) {if(vis[i]) return ;else vis[i] = 1;if(a[i].size() != 2) flag = false;int len = a[i].size();for(int j=0; j<len; j++) {dfs(a[i][j]);}
}
int main() {int n, m;cin >> n >> m;int x, y;for(int i=1; i<=m; i++) {cin >> x >> y;a[x].push_back(y);a[y].push_back(x);}memset(vis, 0, sizeof(vis));int ans = 0;for(int i=1; i<=n; i++) {if(vis[i]) continue;flag = true;dfs(i);if(flag) ans++;}cout << ans << endl;return 0;
}

 

  相关解决方案