coding_test/camera.cpp at boj · bae-jae/coding_test · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <string.h>

using namespace std;

int map[1005][1005];
int visited[1005];
int answer, n;

void init(void)
{
	answer = 0;

	memset(visited, 0, sizeof(visited));
	memset(map, 0, sizeof(map));
}

int dfs(int here)
{
	int child[3] = {0, 0, 0};
	visited[here] = 1;

	for(int i = 0; i < n; ++i)
	{
		if(map[here][i] == 1 && visited[i] == 0)
			++child[dfs(i)];
	}

	if(child[0] != 0)
	{
		++answer;
		return 2;
	}

	if(child[2] != 0)
		return 1;

	return 0;
}

int main(void)
{
	int tc;
	cin >> tc;

	for(int test = 0; test < tc; ++test)
	{
		int k;
		cin >> n >> k;

		init();

		for(int i = 0; i < k; ++i)
		{
			int here, there;
			cin >> here >> there;

			map[here][there] = 1;
			map[there][here] = 1;
		}

		for(int i = 0; i < n; ++i)
		{
			if(!visited[i] && dfs(i) == 0)
				++answer;

		}

		cout << answer << "\n";
	}
}