[SWEA] (C++) D4 7465 창용 마을 무리의 개수

union-find , graph 문제이다.

union-find로 풀 경우, 들어오는 대로 union하여 그룹을 만든후, 그룹의 수를 세면 된다.

graph로 풀 경우, 양방향 그래프를 만들어 준 후, dfs 탐색 하여 그룹의 수를 확인한다.

여기 코드는 graph로 풀은 경우이다.

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

bool visited[101];

void DFS(vector<vector<int>> G, int index)
{
	visited[index] = true;
	for (int i = 0; i < G[index].size(); i++)
		if (!visited[G[index][i]])
			DFS(G, G[index][i]);
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int test_case;
	int T;

	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		memset(visited, false, sizeof(visited));
		int N, M; cin >> N >> M;
		vector<vector<int>> GRAPH(N + 1, vector<int>());
		int start, end, out = 0;
		for (int i = 0; i < M; i++)
		{
			cin >> start >> end;
			GRAPH[start].push_back(end);
			GRAPH[end].push_back(start);
		}

		for(int i = 1; i <= N; i++)
			if (!visited[i])
			{
				out++;
				DFS(GRAPH, i);
			}

		cout << '#' << test_case << ' ' << out << '\n';
	}
	return 0;
}