Codeforces Round #479 (Div. 3) E. Cyclic Components (思维,DFS)

题意:给你\(n\)个顶点和\(m\)条边,问它们有多少个单环(无杂环),例如图中第二个就是一个杂环.

题解:不难发现,如果某几个点能够构成单环,那么每个点一定只能连两条边.所以我们先构建邻接表,然后从某个数开始跑dfs,如果这一边所有点的度数都为\(2\),那么就能构成一个单环.

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
using namespace std;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;int n,m;
int u,v;
bool st[N];
bool ok=1;
vector<int> V[N];void dfs(int x){
    st[x]=true;
    if(V[x].size()!=2) ok=0;    for(auto w:V[x]){
        if(!st[w]) dfs(w);
    }
}int main() {
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
     while(m--){
        cin>>u>>v;
         V[u].pb(v);
         V[v].pb(u);
     }
     int ans=0;
     for(int i=1;i<=n;++i){
         ok=1;
         if(!st[i]){
             dfs(i);
             if(ok) ans++;
         }
     }    printf("%d\n",ans);    return 0;
}