백준 Gold 4 트리

트리 (백준 Gold 4)

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

정점의 개수 N과 간선의 정보가 M개 주어진다
해당하는 데이터의 정보에 따라서
‘트리’가 몇개 존재하는지를 출력하는 문제

• 입력의 끝은 0,0
  
• 트리는 ‘사이클’이 존재하지 않아야 함
  

풀이 방법

일단 ‘사이클’과 관련된 문제이므로
사이클 판별을 위하여 ‘분리집합’을 사용하였다

또한 트리의 판별 조건을 한번 더 생각하였는데

• 자기 자신이 부모인 노드가 존재한다면 Tree로 정의 가능
  (Root)
  

• 그렇기에 자기 자신이 부모인 노드의 개수를 찾으면 됨
  

다만, ‘사이클’을 체크하기 위하여
사이클이 발생한 경우는 -1로 바꿔주었기에 코드를 추가로 수정하였다

부모를 -1로 바꿔주고 FindParent를 호출하여 재귀적으로 -1로 변경
(어차피 사이클 발생한 경우는 트리로 세지 않으므로)

• 원래는 개수를 세려 하였으나
  개수를 세는 방식은 ‘이미 사이클이 발생한 트리’와
  정상적인 트리에 적용하는 방식이 어렵기에
  포기하였다
  

제출 코드

#include<iostream>
#include<vector>

using namespace std;

int FindParent(vector<int>& pv, int x)
{
	if (x == -1)
		return x;

	if (pv[x] == x)
		return x;

	return pv[x] = FindParent(pv, pv[x]);
}

bool Union(vector<int>& pv, int a, int b)
{
	a = FindParent(pv, a);
	b = FindParent(pv, b);

	if (a == b)
		return false;

	if (a == -1 ||
		b == -1)
	{
		return false;
	}

	pv[a] = b;
	return true;
}

int main()
{
	int idx = 1;

	while (true)
	{
		int n, m;
		cin >> n >> m;
		if (n == 0 &&
			m == 0)
		{
			break;
		}

		vector<int> pv(n);
		for (int i = 0; i < n; i++)
			pv[i] = i;

		for (int i = 0; i < m; i++)
		{
			int t1, t2;
			cin >> t1 >> t2;
			t1--;
			t2--;
			if (Union(pv,t1,t2) == false)
			{
				int x1 = FindParent(pv, t1);
				int x2 = FindParent(pv, t2);
				// 사이클이 발생한 녀석들
				if(x1 != -1)
					pv[x1] = -1;

				if(x2 != -1)
					pv[x2] = -1;
			}
		}

		for (int i = 0; i < n; i++)
			FindParent(pv, i);

		int ans = 0;

		for (int i = 0; i < n; i++)
		{
			if (pv[i] == i)
				ans++;
		}

		cout << "Case " << idx << ": ";

		if (ans >= 2)
			cout << "A forest of " << ans << " trees." << '\n';
		else if (ans == 1)
			cout << "There is one tree." << '\n';
		else
			cout << "No trees." << '\n';

		idx++;
	}

	return 0;
}

결과

이전에 풀었던 문제들보다는
‘사이클’과 ‘트리’에 더 집중한 계열의 문제였다