[BOJ 4803] 트리

#1 .DFS

 

[ 접근법 ]

1. 각 정점을 양방향으로 저장한다.

2. 이전 노드(before)을 저장하여, 연결되는 노드들은 패스 해준다.

(1,2 -> 2,3 일 경우, 2의 visited는 true이기 때문에 이를 방지)

3. 사이클이 생기는 경우, true를 만환

(자식 노드가 이미 방문했거나, 깊이 탐색으로 내려가던 중 자식이 방문되었을 경우)

(1,2 -> 2,3 -> 1,3 인 경우, 3(자식)이 visited가 true이므로)

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX 501

vector<int> v[MAX];
int parent[MAX] = { 0, };
bool visited[MAX];

void init() {
	for (int i = 0; i < MAX; i++) {
		parent[i] = 0;
		visited[i] = false;
		v[i].clear();
	}
}

bool dfs(int current, int before) {

	visited[current] = true;

	for (int i = 0; i < v[current].size(); i++) {
		int child = v[current][i];
		// 1,2 -> 2,3 일 경우 2의 visited가 true이기 때문에 이를 방지
		if (child == before) {
			continue;
		}

		// 사이클이 생김
		if (visited[child])	return true;
		
		// 깊이 탐색으로 가면서, 방문한 곳을 또 방문(사이클) 생성되면, true
		if (dfs(child, current)) {
			return true;
		}

	}


	return false;
}

int main() {
	int idx = 1;
	while (1) {
		init();
		int N, M;
		cin >> N >> M;
		bool chk[MAX] = { false, };
		bool flag = false;

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

		for (int i = 0; i < M; i++) {
			int a, b;
			cin >> a >> b;

			v[a].push_back(b);
			v[b].push_back(a);

		}

		int cnt = 0;


		for (int i = 1; i <= N; i++) {
			if (!visited[i]) {
				if (!dfs(i, 0)) {
					
					cnt++;
				}
			}

		}



		cout << "Case " << idx++ << ": ";
		if (cnt == 1) cout << "There is one tree." << "\n";
		else if (cnt == 0) cout << "No trees." << "\n";
		else cout << "A forest of " << cnt << " trees." << "\n";
	}
}

 

---

#2. 유니온 파인드