기존 Union Find 에서 Group관련 기능이 추가된 code
|
static class DJS{ int[] mom; // grouping int[] cnt; // member count int gnum; // group count public DJS(int n) { mom = new int[n+1]; cnt = new int[n+1]; gnum = n; for (int i = 1; i < n; i++) { mom[i] = i; cnt[i] = 1; } } public int getMom(int n){ if(n==mom[n]) return n; mom[n] = getMom(mom[n]); return mom[n]; } public boolean isSame(int a, int b){ return (getMom(a)==getMom(b)); } public void union(int a, int b){ a = getMom(a); b = getMom(b); if(a == b) return; else if(cnt[a]>=cnt[b]) { mom[b] = a; cnt[a]+=cnt[b]; } else { mom[a] = b; cnt[b]+=cnt[a]; } gnum--; } public int getGroupNum() { return gnum; } public int getGrMemberCnt(int n){ return cnt[getMom(n)]; } |