Submission #55501

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
int m = s.nextInt();
int r = s.nextInt();
UnionFind unionFind = new UnionFind(n+1);
for ( int i = 0; i < r; i++ ) {
int a = s.nextInt();
int b = s.nextInt();
if ( unionFind.isUnited(m, a) || unionFind.isUnited(m, b) ) {
unionFind.unite(a, b);
}
}
System.out.println(unionFind.getSize(m));
}
}
class UnionFind {
protected int[] data;
public UnionFind(int n) {
data = new int[n+1];
for (int i = 0; i < n; i++) {
data[i] = -1;
}
}
public boolean unite(int x, int y) {
int rootX = getRoot(x);
int rootY = getRoot(y);
if ( rootX == rootY ) return false;
if ( data[rootY] < data[rootX] ) {
int tmp = rootX;
rootX = rootY;
rootY = tmp;
}
data[rootX] += data[rootY];
data[rootY] = rootX;
return true;
}
public int getRoot(int i) {
return ( data[i] < 0 ) ? i : ( data[i] = getRoot(data[i]) );
}
public int getSize(int n) {
return -data[getRoot(n)];
}
public boolean isUnited(int x, int y) {
return getRoot(x) == getRoot(y);
}
}

ステータス

項目 データ
問題 1188 - マジック
ユーザー名 r1825
投稿日時 2019-10-04 12:09:29
言語 Java
状態 Accepted
得点 1
ソースコード長 1468 Byte
最大実行時間 134 ms
最大メモリ使用量 15672 KB

セット

セット 得点 Cases
1 ALL 1 / 1 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.text AC 131 ms 15452 KB
1
in02.text AC 119 ms 15604 KB
1
in03.text AC 127 ms 15476 KB
1
in04.text AC 134 ms 15248 KB
1
in05.text AC 126 ms 15488 KB
1
in06.text AC 126 ms 15372 KB
1
in07.text AC 132 ms 15672 KB
1
sample1.text AC 129 ms 15560 KB
1
sample2.text AC 130 ms 15452 KB
1
sample3.text AC 122 ms 15524 KB
1