트리_그래프가 트리인지 확인하는 방법

그래프가 트리인지 확인하는 방법

- 트리는 노드 N개, 간선 N-1개를 가지면서 사이클이 없는 특징을 가진다.

- 따라서 사이클이 있다면(탐색하는 과정에서 부모 이외의 이전에 방문했던 노드를 또 방문하게 된다면) 이는 트리가 아닌 그래프이다.

 

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

int N, M;
vector<vector<int>> graph(15, vector<int>(0));
vector<bool> visited(15, false);
vector<int> parent(15, 0);

void setGraph() {

    scanf("%d %d", &N, &M);
    for (int i=0; i<M; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
}

bool bfs(int st) {

    queue<int> q;
    q.push(st);
    visited[st] = true;

    while (!q.empty()) {

        int cur = q.front();
        q.pop();

        for (int i=0; i<graph[cur].size(); i++) {
            int next = graph[cur][i];
            
            //이미 방문한 노드를 재방문하려 할 때, 
            //그 노드가 부모 노드가 아니라면 이는 사이클 그래프 이므로 트리가 아님
            if (visited[next]) {
                if (next == parent[cur]) continue;
                return false; 
            }
            q.push(next);
            visited[next] = true;
            parent[next] = cur;
        }
    }
    return true;
}

int main() {

    setGraph();

    int tree = 0, notTree = 0;
    for (int i=1; i<=N; i++) {
        if (visited[i]) continue;
        if (bfs(i)) tree++;
        else notTree++;
    }

    cout<<"tree 개수: "<<tree<<endl;
    cout<<"notTree 개수: "<<notTree<<endl;
    return 0;
}

/*
input: 
10 8
1 2
1 3
4 5
4 6
5 7
7 6
8 9
8 10

output:
tree 개수: 2
notTree 개수: 1
*/