結果
問題 | No.2563 色ごとのグループ |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2024-02-03 01:07:10 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 1,631 ms / 2,000 ms |
コード長 | 2,684 bytes |
コンパイル時間 | 2,593 ms |
コンパイル使用メモリ | 79,360 KB |
実行使用メモリ | 66,328 KB |
最終ジャッジ日時 | 2024-09-28 10:43:31 |
合計ジャッジ時間 | 29,587 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 133 ms
53,676 KB |
testcase_01 | AC | 134 ms
53,624 KB |
testcase_02 | AC | 138 ms
53,972 KB |
testcase_03 | AC | 135 ms
53,560 KB |
testcase_04 | AC | 136 ms
53,968 KB |
testcase_05 | AC | 133 ms
53,792 KB |
testcase_06 | AC | 140 ms
53,972 KB |
testcase_07 | AC | 132 ms
54,256 KB |
testcase_08 | AC | 140 ms
53,592 KB |
testcase_09 | AC | 173 ms
53,848 KB |
testcase_10 | AC | 147 ms
53,868 KB |
testcase_11 | AC | 184 ms
53,832 KB |
testcase_12 | AC | 167 ms
53,836 KB |
testcase_13 | AC | 167 ms
54,440 KB |
testcase_14 | AC | 253 ms
56,528 KB |
testcase_15 | AC | 204 ms
44,320 KB |
testcase_16 | AC | 209 ms
43,940 KB |
testcase_17 | AC | 214 ms
43,620 KB |
testcase_18 | AC | 197 ms
43,160 KB |
testcase_19 | AC | 250 ms
46,140 KB |
testcase_20 | AC | 370 ms
48,272 KB |
testcase_21 | AC | 304 ms
47,700 KB |
testcase_22 | AC | 282 ms
47,308 KB |
testcase_23 | AC | 355 ms
47,360 KB |
testcase_24 | AC | 975 ms
58,456 KB |
testcase_25 | AC | 891 ms
59,292 KB |
testcase_26 | AC | 1,047 ms
61,188 KB |
testcase_27 | AC | 1,116 ms
64,784 KB |
testcase_28 | AC | 1,172 ms
61,252 KB |
testcase_29 | AC | 1,449 ms
63,672 KB |
testcase_30 | AC | 1,373 ms
66,328 KB |
testcase_31 | AC | 1,327 ms
64,164 KB |
testcase_32 | AC | 1,373 ms
64,500 KB |
testcase_33 | AC | 1,598 ms
57,948 KB |
testcase_34 | AC | 1,625 ms
57,468 KB |
testcase_35 | AC | 1,500 ms
57,716 KB |
testcase_36 | AC | 1,631 ms
57,484 KB |
testcase_37 | AC | 1,606 ms
58,768 KB |
ソースコード
import java.io.PrintWriter;import java.util.*;public class Main {public static void vectorPrint(Vector lis){PrintWriter out = new PrintWriter(System.out);for (int i=0 ; i<lis.size() ; i++){out.print(lis.get(i));if ( i != lis.size()-1){out.print(' ');}else{out.print('\n');}}out.flush();}public static void main(String[] args){Scanner sc = new Scanner(System.in);int N = Integer.parseInt(sc.next());int M = Integer.parseInt(sc.next());int[] C = new int[N];for (int i=0; i<N ;i++){C[i] = Integer.parseInt(sc.next());}Dsu uf = new Dsu(N);for (int i=0; i<M ; i++){int u = Integer.parseInt(sc.next());int v = Integer.parseInt(sc.next());u--;v--;if (C[u] == C[v]){uf.merge(u, v);}}Map<Integer,Integer> dic = new HashMap<>();for (int i=0; i<N ; i++){if (uf.leader(i) == i){if (!dic.containsKey(C[i])){dic.put(C[i], 0);}dic.put(C[i], dic.get(C[i]) + 1);}}int ans = 0;for (Map.Entry<Integer,Integer> tup : dic.entrySet()){ans += tup.getValue();ans -= 1;}System.out.println(ans);}}class Dsu {int n;int[] p;int[] s;Dsu(int N) {this.n = N;this.p = new int[N];this.s = new int[N];for (int i=0; i<N ; i++){this.p[i] = i;this.s[i] = 1;}}public int leader(int a){Vector<Integer> visit = new Vector<Integer>();while (this.p[a] != a){visit.addElement(a);a = this.p[a];}for (Integer v: visit){this.p[v] = a;}return a;}public int merge(int a,int b){int pa = this.leader(a);int pb = this.leader(b);if (pa == pb){return pa;}else if (this.s[pa] >= this.s[pb]){this.s[pa] += this.s[pb];this.p[pb] = pa;return pa;}else{this.s[pb] += this.s[pa];this.p[pa] = pb;return pb;}}public Boolean same(int a, int b){int pa = this.leader(a);int pb = this.leader(b);return (pa == pb);}public int size(int a){int pa = this.leader(a);return this.s[pa];}}