結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
権限があれば一括ダウンロードができます

ソースコード

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(i + ":" + 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