Graph [Adjacency List] - 4803 C++

문제

---

4803번

트리는 사이클이 없는 연결 요소이다.

트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점에 대해서 경로가 유일하다.

그래프가 주어졌을 때, 트리의 개수를 세는 프로그램을 작성하시오.

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

4803번: 트리

 

 

 

개요

---

 

유니온 파인드라는 알고리즘을 이용하면 쉽게 답이 나온다는데... 필자는 이런 알고리즘의 존재를 문제 다 풀고 나서 알았다

(Union-Find : 두 노드가 같은 그래프에 속한지 알아내는 알고리즘)

 

문제 속에 답에 대한 힌트가 크게 주어져있다.

트리의 특징으로 vertex가 n개 라면 edge는 반드시 n-1이라는 걸 이용해서 풀면 금방 풀 수 있다.

 

사실 필자는 그냥 주어진 문제만 보고 Directed-Graph로도 풀 수 있을 것 같아서 풀어보려 했다.

(다만 여러 가지 여러가지 예외 사항이 많다는 걸 대략 15번 정도 제출하고 나서 알았다......)

 

내가 한 실수는 이렇다.

Directed 이기 때문에 boolean 타입의 배열을 만들고 방문한 노드는 전부 true로 처리하게 될 경우

만약 내 다음 노드가 true라면 그 그래프는 사이클이 있으니까 tree가 아니다.

여기에서 발생한 문제는 루트노드가 1이 아닌 다른 노드일 수도 있지만 필자가 작성한 코드는 루트노드가 1일 경우만을 고려해서 작성한 것이다.

이 예외사항을 알고 나서는 절대로 Directed-Graph로는 풀 수 없다는 것을 알았다.

문제를 풀 땐 문제에 나와있는 예제만 보지 말고 모든 경우의 수를 다 확인해 보자......

 

 

 

 

과정

---

실수를 토대로 Undirected-Graph를 만든다.

이때, 인접행렬을 사용할지 인접리스트를 사용할지는 개인의 선택이다.

나는 리스트가 익숙하기도 하고 간선의 가중치가 따로 없기 때문에 인접 리스트를 이용했다.

트리의 간선 개수는 vertex - 1이 맞다. 하지만 Undirected-Graph는 양방향으로 각각의 vector에 추가해야 하기 때문에 간선의 개수는 두 배가 된다.

따라서, 간선이 만약 2*(vertex-1) 보다 많다면 사이클이 생기므로 그래프가 트리가 아니게 된다.

왼쪽은 트리X 오른쪽은 트리O

DFS를 이용해 입력에서 주어진 노드들을 순회하며 연결되어 있는 간선의 개수를 세고 트리인지 아닌지 판별하면 답이 나오게 된다.

for문으로 모든 노드에 대하여 DFS를 실행하되, 이미 visited 배열에 true로 체크되어 있는 노드는 DFS를 실행하지 않아야 한다.

 

 

 

 

코드

---

#include<iostream>
#include<vector>
using namespace std;
bool visited[1001];
int node = 0;
int inEdge = 0;

void dfs(int cur, vector<int> graph[]){ //DFS
    visited[cur]= true;
    inEdge+=1;
    node+=1;
    for(int i = 0; i<graph[cur].size();i++){
        int next = graph[cur][i];
        if(visited[next]){
            inEdge +=1; 
            continue;
        }
        dfs(next,graph);
    }
}

int main(){
    int n, m, first, second;
    cin >> n >> m;
    int ca = 0;
    while(n!=0 || m!= 0){
        ca +=1;
        int tree = 0;
        vector<int> graph[1001];
        
        for(int i = 0; i< m; i++){ //UnDirection Graph 이므로 양방향 간선
            cin >> first >> second;
            graph[first].push_back(second);
            graph[second].push_back(first);
        }
        for(int i = 1; i<=n; i++){ //각각의 노드에 DFS 실행하되, 이미 방문한 노드는 제외
            if(visited[i] == false){
                dfs(i, graph);
                if(node*2>inEdge){
                    tree +=1;
                }
                node = 0; 
                inEdge = 0;
            }
        }
        if(tree == 0){
            cout << "Case " << ca << ": No trees.\n";
        }
        else if( tree == 1){
            cout << "Case " << ca << ": There is one tree.\n";
        }
        else{
            cout << "Case " << ca << ": A forest of " << tree << " trees.\n";
        }
        node = 0; inEdge = 0; //한번의 테스트케이스가 끝나면 반드시 초기화 할 것
        for(int i = 1; i <= n; i++)
            visited[i] = false;
        cin >> n >> m;
    }
}