https://algospot.com/judge/problem/read/BRAVE
algospot.com :: BRAVE
용감한 쿠키군의 폭탄 해체 문제 정보 문제 당신은 용감한 쿠키군을 둘러싼 시한 폭탄을 해체해야 한다. 용감한 쿠키군을 둘러싼 폭탄은 1부터 N까지 번호가 적혀 있는 금속 점을 갖고 있다. 또한, 그 점들 중 일부는 전선들로 이어져 있다. 당신은 주변을 둘러보던 중 테러리스트가 남긴 쪽지를 발견했고, 폭탄의 특징을 알게 되었다. 그 특징들은 다음과 같다. 금속 점 x와 y가 직접 전선으로 연결되어 있으면, x와 y 사이에는 전류가 흐른다. 금속 점 x와 y
algospot.com
용감한 쿠키군의 폭탄 해체
생각보다 어렵게 되지는 않았음.
Union-find 내에 Union시 Max group의 Size를 갱신하는 문제로 수정함.
생각보다 간단
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class brave {
static int N, M;
static DJS djs;
static class DJS {
int[] mom;
int[] cnt;
int group, maxgr=0;
DJS(int n) {
mom = new int[n+1];
cnt = new int[n+1];
for (int i = 1; i <= n ; i++) {
mom[i] = i;
cnt[i] = 1;
}
group = n;
maxgr = 0;
}
int find(int n) {
if (n == mom[n]) return n;
return mom[n] = find(mom[n]);
}
int getCnt(int n) {
return cnt[n];
}
boolean union(int a, int b) {
a = find(a);
b = find(b);
if(a==b) return false;
if(getCnt(a)>=getCnt(b)) {
mom[b] = a;
cnt[a] += cnt[b];
maxgr = Math.max(maxgr, cnt[a]);
} else {
mom[a] = b;
cnt[b] += cnt[a];
maxgr = Math.max(maxgr, cnt[b]);
}
group--;
return true;
}
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("res/input_brave.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine().trim());
StringTokenizer st;
for (int t = 1; t <=T ; t++) {
st = new StringTokenizer(br.readLine().trim(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
djs = new DJS(N);
int a, b;
for (int i = 0; i < M ; i++) {
st = new StringTokenizer(br.readLine().trim(), " ");
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
djs.union(a, b);
}
System.out.println(djs.maxgr);
}
}
}