R479(Div.3) E. Cyclic Components

하하하 알고리즘 하나도 기억이 안나서 오늘부터 글을 쓰면서 강제로 기억해야겠다.

쉬운것부터 차근차근 다시 해야지..!

이 문제는 Cycle을 찾는 문제이다. 

조건은 처음시작한 정점으로 마지막에 다시 돌아오는 것인데 중간에 다른 정점으로 빠지는 간선이 존재하면 안된다..!

이 사진중에 (15, 5, 11, 9) / (7, 10, 16) 만이 조건을 만족하는 Cycle이다!

처음에 dfs를 돌리고 (정점*2 == 간선) 했다가 18번째 테케에서 틀렸다 ㅎ

솔루션은

1. 각 정점의 degree를 구한다

2. dfs를 돌리며 방문한점을 벡터에 넣어준다.

3. dfs가 끝난 후 벡터에 들어있는 정점들이 모두 2의 degree를 갖는다면 문제에서 원하는 cycle이다!

이렇게 찾아주면 된다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool check[200020];
int deg[200020];
vector<int> vt;
vector<vector<int>> Graph;
bool ok, ansup;
int n, m;
 
void dfs(int x) {
    check[x] = true;
    vt.push_back(x);
    for (int i = 0; i < Graph[x].size(); i++) {
        if (!check[Graph[x][i]]) dfs(Graph[x][i]);
    }
}
int main() {
    scanf(" %d %d", &n, &m);
    Graph.resize(n);
    for (int i = 0; i < m; i++) {
        int a, b; scanf(" %d %d", &a, &b);
        a--; b--;
        Graph[a].push_back(b);
        Graph[b].push_back(a);
        deg[a]++; deg[b]++;
    }
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (check[i]) continue;
        vt.clear();
        dfs(i);
 
        bool go = true;
        for (int i = 0; i < vt.size(); i++) {
            if (deg[vt[i]] != 2) go = false;
        }
        if (go)ans += 1;
    }
    printf("%d\n", ans);
}