목록DFS (1)

Meme's IT

[SWEA] 창용 마을 무리의 개수

# Union-Find #DFS 문제 창용 마을에는 N명의 사람이 살고 있다. 사람은 편의상 1번부터 N번 사람까지 번호가 붙어져 있다고 가정한다. 두 사람은 서로를 알고 있는 관계일 수 있고, 아닐 수도 있다. 두 사람이 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계라면, 모두 묶어서 하나의 무리라고 한다. 창용 마을에 몇 개의 무리가 존재하는지 계산하는 프로그램을 작성하라. 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 각각 창용 마을에 사는 사람의 수와 서로를 알고 있는 사람의 관계 수를 나타내는 두 정수 N, M(1 ≤ N ≤ 100, 0 ≤ M ≤ N(N-1)/2) 이 공백 하나로 구분되어 주어진다. 이후 M개의 줄에 걸쳐서 서로를 알고 있는 두..
알고리즘/문제풀이 2023. 9. 23. 02:07
이전 Prev 1 Next 다음