백준 4803번 트리

문제 링크입니다: https://www.acmicpc.net/problem/4803

DFS를 통해 정점의 개수와 간선의 개수를 구한 다음 조건 성립하는지 파악하는 문제였습니다.

주의할 점은 DFS를 통해 구한 간선의 개수는 실제 간선의 개수의 두배라는 점입니다.

왜냐하면, 노드를 삽입할 때 어느 노드가 부모노드인지 모르기 때문에 양방향으로 삽입했기 때문입니다!

그리고 벡터 배열을 전역변수로 선언하였다면 while문이 돌 때마다 clear하는 것을 잊지 말아야합니다 ㅠ

#include <iostream>

#include <vector>

#include <cstring> //memset

using namespace std;

 

const int MAX = 500 + 1;

 

int N, M;

bool visited[MAX];

bool passed[MAX]; //간선 지나갔는지 여부

vector<int> tree[MAX];

 

//DFS를 통해 정점 개수 파악

int numOfVertex(int nodeNum)

{

        int cnt = 1;

        visited[nodeNum] = true;

       

        for (int i = 0; i < tree[nodeNum].size(); i++)

        {

                 int next = tree[nodeNum][i];

                 if (!visited[next])

                         cnt += numOfVertex(next);

        }

        return cnt;

}

 

//DFS를 통해 간선 개수 파악

//정점 입력시 두번 입력하므로 여기서 구한 개수는 실제의 2배

int numOfEdge(int nodeNum)

{

        int cnt = tree[nodeNum].size();

        passed[nodeNum] = 1;

 

        for (int i = 0; i < tree[nodeNum].size(); i++)

        {

                 int next = tree[nodeNum][i];

                 if (!passed[next])

                         cnt += numOfEdge(next);

        }

        return cnt;

}

 

int main(void)

{

        int cnt = 1;

 

        while (1)

        {

                 //꼭 비워줍니다...

                 for (int i = 0; i < MAX; i++)

                         tree[i].clear();

 

                 cin >> N >> M;

                 if (N == 0 && M == 0)

                         break;

 

                 for (int i = 0; i < M; i++)

                 {

                         int node1, node2;

                         cin >> node1 >> node2;

 

                         tree[node1].push_back(node2);

                         tree[node2].push_back(node1);

                 }

 

                 memset(visited, false, sizeof(visited));

                 memset(passed, false, sizeof(passed));

 

                 cout << "Case " << cnt++ << ": ";

 

                 int result = 0;

                 for (int i = 1; i <= N; i++)

                 {

                         if (!visited[i])

                         {

                                 int V = numOfVertex(i);

                                 int E = numOfEdge(i);

                                 //트리의 조건

                                 if (V - 1 == E / 2)

                                          result++;

                         }

                 }

 

                 switch (result)

                 {

                 case 0:

                         cout << "No trees." << "\n";

                         break;

                 case 1:

                         cout << "There is one tree." << "\n";

                         break;

                 default:

                         cout << "A forest of " << result << " trees." << "\n";

                         break;

                 }

        }

        return 0;

}

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~