結果

問題 No.556 仁義なきサルたち
ユーザー watarimaycry2watarimaycry2
提出日時 2019-10-02 23:46:55
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 2,016 bytes
コンパイル時間 1,912 ms
コンパイル使用メモリ 77,744 KB
実行使用メモリ 60,764 KB
最終ジャッジ日時 2024-10-03 06:03:58
合計ジャッジ時間 7,670 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 111 ms
54,164 KB
testcase_01 AC 112 ms
53,352 KB
testcase_02 AC 112 ms
54,088 KB
testcase_03 AC 116 ms
53,748 KB
testcase_04 AC 115 ms
53,904 KB
testcase_05 AC 141 ms
54,328 KB
testcase_06 AC 140 ms
53,996 KB
testcase_07 AC 145 ms
54,500 KB
testcase_08 AC 146 ms
54,188 KB
testcase_09 AC 184 ms
55,148 KB
testcase_10 AC 200 ms
54,980 KB
testcase_11 WA -
testcase_12 AC 202 ms
56,776 KB
testcase_13 AC 233 ms
54,772 KB
testcase_14 WA -
testcase_15 AC 304 ms
59,428 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 AC 404 ms
59,328 KB
testcase_19 AC 411 ms
59,324 KB
testcase_20 AC 383 ms
59,328 KB
testcase_21 AC 382 ms
59,556 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;
public class Main {
	public static void myout(Object text){//standard output
		System.out.println(text);
	}
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		//String tmp = sc.next();
		//int tmp = sc.nextInt();
		//Long tmp = sc.nextLong();
      int N = sc.nextInt();
      int M = sc.nextInt();
      UnionFindTree uf = new UnionFindTree(N + 1);
      for(int i = 0; i < M; i++){
        uf.union(sc.nextInt(),sc.nextInt());
      }
      for(int i = 1; i <= N; i++){
        myout(uf.find(i));
      }
      
      
	}
  
}
class UnionFindTree {
	
	int[] parent; //インデックスにとノードを対応させ、そのルートノードのインデックスを格納	
	int[] rank; //parentと同様に、木の高さを格納
	
	UnionFindTree(int size) {
		this.parent = new int[size];
		this.rank = new int[size];
		
		for (int i = 0; i < size; i++) {
			makeSet(i);
		}
	}
	
	void makeSet(int i) {
		parent[i] = i;
		rank[i] = 1; //集合の高さ
	}
	
	void union(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);
		//System.out.println("xr:" + xRoot + ",yr:" + yRoot);
      //System.out.println("xrr:" + rank[xRoot] + ",yrr:" + rank[yRoot]);
		//xが属する木の方が大きい場合
		if (rank[xRoot] > rank[yRoot]) { 
			parent[yRoot] = xRoot; 
			rank[xRoot] += rank[yRoot];					   
		} else if(rank[xRoot] < rank[yRoot]) {
			parent[xRoot] = yRoot;
			rank[yRoot] += rank[xRoot];
		} else if (xRoot != yRoot){
			if(xRoot > yRoot){
              parent[xRoot] = yRoot;
              rank[yRoot]++;
            }else{
              parent[yRoot] = xRoot;
              rank[xRoot]++;
            }
		}
      //System.out.println("xrr:" + rank[xRoot] + ",yrr:" + rank[yRoot]);
	}
	
	//引数の属する木のルートのidを返す
	int find(int i) {
		if (i != parent[i]) {
			parent[i] = find(parent[i]);
		}
		return parent[i];
	}
	
	//同じ木に属しているか
	boolean same(int x, int y) {
		return find(x) == find(y);
	}
}
0