Boj 33579 디미그래프 c++

https://www.acmicpc.net/problem/33579

문제

주어진 그래프가 다음 조건을 만족시키는지 확인해야 한다.

1. 임의의 서로 다른 두 정점을 연결하는 경로가 하나 이상 존재한다.
2. 사이클이 오직 하나 존재한다.
3. 사이클에 포함되는 정점과 사이클에 포함되지 않는 정점을 연결하는 간선은 정확히 하나 존재한다.
4. 사이클에 포함되지 않는 정점의 차수는 2 이하이다.

 

즉, 사이클이 하나 있고 여기에 꼬리가 하나 달린 올챙이 모양 그래프인지 판별하라는 것이다.

 

접근 & 풀이

처음에는 3번 조건을 간과한 채로 막연하게 

"아하, 올챙이 모양이니까 차수가 3인 정점이 1개, 차수가 1인 정점이 한개, 그리고 나머지가 차수가 2라면 조건을 만족하겠구나!"

라는 생각으로 구현했다가 80% 언저리에서 틀리고 왜 틀렸는지 고민했었다.

 

3번 조건에서는 분명히 "사이클에 포함되지 않는 정점과 사이클에 포함되는 정점을 연결하는 간선은 정확히 하나 존재한다"

라고 명시하였다.

 

그리고 2번 조건에서도 "사이클은 오직 하나만 존재한다" 라고 명시하였다.

 

즉, 컴포넌트 수가 1개 이상이면 안된다는 사실을 놓친 것이다.

나는 두번째 시도에서 그러면 정점의 개수 - 2가 차수가 2인 정점의 개수와 같으면 조건을 만족하겠구나라고 생각하고 또다시

코드를 제출했다. 결과는 당연하게도 WA.

 

차수로 계산하더라도 올챙이 하나와 완전한 사이클들로 이루어진 반례를 제외하지는 못하는 것이다.

 

때문에, dfs로 연결요소의 개수가 1개인지 먼저 체크해주어야 한다.

 

#include <bits/stdc++.h>
using namespace std;

int cnt = 0;
vector<vector<int>> connected;
map<int, bool> visited;

void dfs(int n) {
    visited[n] = true;
    cnt++;
    for(int nx : connected[n]) {
        if(!visited[nx])
            dfs(nx);
    }
}

int main() {

    int N, M, s = 0, e = 0;
    cin >> N >> M;
    connected.resize(N+1);

    for(int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        connected[v].push_back(u);
        connected[u].push_back(v);
    }
    dfs(1);
    if(cnt != N) {
        cout << "NO";
        return 0;
    }
    for(int i = 1; i <= N; i++) {
        int num = connected[i].size();
        if(num == 3) {
            e++;
            continue;
        }
        if(num == 2)continue;
        if(num == 1) {
            s++;
            continue;
        }
        else {
            cout << "NO";
            return 0;
        }
    }
    if(s == 1 && e == 1)cout << "YES";
    else
        cout << "NO";
}

 

 

반례처리에 약한 것 같다.

많이 연습해보자.