[백준 4803] 트리

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

1)문제 분류

- 트리

2)문제 해결

- 처음에는 어떻게 부분트리의 개수를 알수 있을까.. 고민을 했다..고민끝에.. 해답을 봐버렸다!

  해답을 본 결과, 이 문제는 트리의 성질을 이용해야하는데,   

  트리의 성질중에  트리는 정점이 n개, 간선이 n-1개 일때 성립하는게 있다.

  그래서, 각 정점마다 정점의 개수를 구하고, 간선의 개수를 구해서 비교하면 트리가 성립되는지 안되는지를 알수있는 문제였다!

  정점의 개수와 간선의 개수를 구하는 방법은 dfs로 해결 할 수가 있었는데,

  정점의 개수는 연결되어있는 정점을 찾아갈때마다 cnt를 +1하는 방식으로 개수를 구할수 있다

  간선의 개수 cnt를 +해당 노드에 연결 되어있는 노드의 개수를  더하면 구할 수있다. 

  하지만, vector에 양방향으로 연결노드를 만들어놨기때문에 , 간선의 개수는 나누기(/)2를해서 간선의 개수를 파악해야한다.

 #include<iostream>

#include<algorithm>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

int n, m;

vector<int>vt[502];

bool visit1[502];

bool visit2[502];

int cntnode(int node) //정점개수구하기

{

int cnt = 1;

visit1[node] = true;

for (int i = 0; i < vt[node].size(); i++)

{

int next = vt[node][i];

if (visit1[next] == false)

{

cnt+=cntnode(next);

    }

}

return cnt;

}

int cntedge(int node) //간선 개수구하기 

{

int cnt = vt[node].size();

visit2[node] = true;

for (int i = 0; i < vt[node].size(); i++)

{

int next = vt[node][i];

if (visit2[next] == false)

{

cnt += cntedge(next);

}

}

return cnt;

}

int main()

{

int test = 0;

while (1)

{

for (int i = 0; i <= 500; i++)vt[i].clear();

test++;

cin >> n >> m;

if (n == 0 && m == 0)return 0;

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

{

int x, y;

cin >> x >> y;

vt[x].push_back(y);

vt[y].push_back(x);

}

memset(visit1, false, sizeof(visit1));

memset(visit2, false, sizeof(visit2));

int result = 0;

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

{

if (visit1[i] == false)

{

int V = cntnode(i);//정점의 개수

int E = cntedge(i); //간선의 개수

if (V - 1 == (E / 2))

{

result++;

}

}

}

cout << "Case " << test << ": ";

if (result == 0)cout << "No trees.";

else if (result == 1)cout << "There is one tree.";

else cout << "A forest of " << result << " trees.";

cout << "\n";

}

}