結果
| 問題 | No.2290 UnUnion Find |
| ユーザー |
 kusagame12
|
| 提出日時 | 2024-06-11 12:41:43 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 4,131 bytes |
| コンパイル時間 | 3,102 ms |
| コンパイル使用メモリ | 76,900 KB |
| 実行使用メモリ | 68,128 KB |
| 最終ジャッジ日時 | 2024-06-11 12:41:58 |
| 合計ジャッジ時間 | 12,277 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 123 ms
47,040 KB |
| testcase_01 | AC | 121 ms
41,336 KB |
| testcase_02 | AC | 1,553 ms
57,704 KB |
| testcase_03 | AC | 1,697 ms
60,064 KB |
| testcase_04 | TLE | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
ソースコード
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int q = sc.nextInt();
UnionFindTree uft = new UnionFindTree(n);
for (int j=0; j<q; j++) {
if(sc.nextInt() == 1){
int u = sc.nextInt()-1;
int v = sc.nextInt()-1;
uft.union(u , v);
}else{
int v = sc.nextInt()-1;
int connectCnt = uft.getSize(v);
if(connectCnt != n){
for (int i=0; i<n; i++) {
if(!uft.same(v , i)){
System.out.println(i+1);
break;
}
}
}else{
System.out.println(-1);
}
}
}
}
}
//Union find クラス
class UnionFindTree {
int[] parent; // インデックスとノードを対応させ、そのルートノードのインデックスを格納
int[] rank; // parentと同様に、木の高さを格納
int[] size; // 木を構成する、要素の数を格納
int treeCount; // 木の数
/**
* コンストラクタ
*
* @param n : 頂点の数
*/
public UnionFindTree(int n) {
this.parent = new int[n];
this.rank = new int[n];
this.size = new int[n];
this.treeCount = n;
// 根を作る。
for (int i = 0; i < n; i++) {
makeSet(i);
}
}
/**
* 根をつくる。最初は、すべて異なる木に属しているものとする。
*
* @param i : 頂点の数
*/
private void makeSet(int i) {
parent[i] = i;
rank[i] = 0; // 集合の高さ
size[i] = 1; // 木を構成する要素の数
}
/**
* 要素xが属する木と要素yが属する木を連結する。 木の高さ（ランク）を気にして、低い方に高い方をつなげる。（高い方の木を全体の木とする。）
*
* @param x : １つ目の要素(yとは異なる木に属している必要がある。)
* @param y : ２つ目の要素(xとは異なる木に属している必要がある。)
*/
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
int xSize = getSize(xRoot);
int ySize = getSize(yRoot);
// xが属する木の方が大きい場合
if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot; // yの親をxに更新
size[xRoot] = xSize + ySize; // 木を構成する要素の数を更新
treeCount--;
} else if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
size[yRoot] = ySize + xSize;
treeCount--;
} else if (xRoot != yRoot) {
parent[yRoot] = xRoot;
rank[xRoot]++; // 同じ高さの木がルートの子として着くから大きさ++;
size[xRoot] = xSize + ySize;
treeCount--;
}
}
/**
* 要素の根を返す。 経路圧縮も同時に行う。（1→3→2となっていて2をfindした際、1→3,2と木の深さを浅くする。）
*
* @param i
* @return 要素iの根 （1→3→2となっていて2をfindした際、1となる。)
*/
public int find(int i) {
if (i != parent[i]) {
parent[i] = find(parent[i]);
}
return parent[i];
}
/**
* ２つの要素が同じ木に属するかどうかを返す。
*
* @param x : １つ目の要素
* @param y : ２つ目の要素
* @return 同じ木に属していればtrue
*/
public boolean same(int x, int y) {
return find(x) == find(y);
}
/**
* 木の高さを返す。
*
* @param i : 高さを調べたい木の根の番号
* @return 木の高さ
*/
public int getRank(int i) {
return rank[i];
}
/**
* 木を構成する要素の数を返す。
*
* @param i : 要素数を調べたい木の根の番号
* @return 木を構成する要素の数
*/
public int getSize(int i) {
return size[find(i)];
}
/**
* 木の数を返す。
*
* @return 木の数。
*/
public int getTreeCount() {
return treeCount;
}
}