알고리즘
[Java] SWEA - 창용 마을 무리의 개수
J3SUNG
2023. 3. 2. 02:15
728x90
N명의 사람들이 서로 관계가 이어져 있습니다.
이 때 서로 아는 관계이거나 몇 사람을 거쳐서 알 수 있는 관계는 하나의 무리로 판단합니다.
무리의 수를 찾는 문제입니다.
이어진 관계를 따라가서 전부 방문처리해주고 카운트를 해주었습니다.
모든 사람을 기준으로 위의 과정을 하고 카운트 된 값을 출력해주었습니다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Solution {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int testcase = Integer.parseInt(br.readLine());
for(int t=1; t<=testcase; ++t) {
bw.write("#" + t + " ");
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] p = new int[n+1];
int ans = 0;
for(int i=1; i<=n; ++i) {
p[i] = i;
}
for(int i=0; i<m; ++i) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int rootA = a;
int rootB = b;
while(rootA != p[rootA]) {
rootA = p[rootA];
}
while(rootB != p[rootB]) {
rootB = p[rootB];
}
if(rootA < rootB) {
p[rootA] = rootB;
} else if (rootA > rootB) {
p[rootB] = rootA;
}
}
for(int i=1; i<=n; ++i) {
if(p[i] == i) {
++ans;
}
}
bw.write(ans + "\n");
}
bw.close();
}
}