BOJ 13244 - Tree [C++]

문제

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

 

그래프가 주어지면, 트리인지 아닌지 판별하는 문제다.

multiedge가 주어질 수 있다는 점에 유의해야 한다.

풀이

트리인지 판별하는 가장 간단하고 쉬운 방법은 분리 집합을 이용하는 것이라 생각한다.

union 연산이 정확히 N-1번 발생함과 동시에 간선의 개수가 N-1개라면, 주어진 그래프는 트리이다.

 

#include <iostream>
#include <functional>
#include <numeric>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int T, N, M, a, b, r[1001]{};
    function<int(int)> f = [&](int x) -> int { return x == r[x] ? x : r[x] = f(r[x]); };
    for (cin >> T; T--;) {
        cin >> N >> M;
        int cnt = 0;
        for (iota(r, r + N + 1, 0); M--;) {
            cin >> a >> b;
            int x = f(a), y = f(b);
            if (x == y) cnt += N;
            else r[x] = y, cnt++;
        }
        cout << (cnt == N - 1 ? "tree\n" : "graph\n");
    }

}