문제

문제 링크

해설

트리는 그래프의 일종임을 바탕으로 주어진 입력이 그래프인지, 트리인지 식별하는 문제입니다.

• 문제에서는 '연결성' + '간선이 1개만 연결됨' + '간선 추가하면 사이클 생성됨' 세 가지 구분법을 제공합니다.
• '트리의 모든 노드는 연결돼있다'라는 정보와 '트리의 모든 노드는 1개의 간선으로 연결돼있다'는 정보는 특히 중요합니다.
• N개의 노드가 간선 1개로 연결돼있기 위해서는 간선은 '반드시 N - 1개'여야 한다는 점을 유추할 수 있기 때문입니다!
• 따라서, 주어진 간선 정보 M이 N - 1개인지 확인한 뒤,
• 모든 노드가 연결돼있기 때문에 DFS 1회에 모든 노드를 순회할 수 있는지 검사하면 됩니다.

코드

#include <iostream>
#include <vector>
using namespace std;

void DFS(int s, const vector<vector<int>>& adj, vector<bool>& visited) {
    visited[s] = true;
    for (auto d : adj[s])
        if (!visited[d]) DFS(d, adj, visited);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int N, M;
        cin >> N >> M;

        vector<vector<int>> adj(N + 1);
        for (int i = 0; i < M; ++i) {
            int s, e;
            cin >> s >> e;
            adj[s].push_back(e);
            adj[e].push_back(s);
        }
        vector<bool> visited(N + 1);
        int dfsCount = 0;
        for (int i = 1; i <= N; ++i) {
            if (!visited[i]) {
                DFS(i, adj, visited);
                dfsCount++;
            }
        }
        // Tree 조건에 따라 M == N - 1이고 DFS 1회에 모든 노드를 방문할 수 있어야 함.
        if (M == N - 1 && dfsCount == 1) cout << "tree\n";
        else cout << "graph\n";
    }
}

소스코드 링크

결과