結果

問題 No.556 仁義なきサルたち
ユーザー youthfuldays072
提出日時 2018-06-28 16:28:50
言語 Java
(openjdk 23)
結果
AC  
実行時間 451 ms / 2,000 ms
コード長 5,031 bytes
コンパイル時間 3,264 ms
コンパイル使用メモリ 90,896 KB
実行使用メモリ 59,588 KB
最終ジャッジ日時 2024-06-30 23:29:50
合計ジャッジ時間 9,458 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		int M = sc.nextInt();

		int[] A = new int[M];
		int[] B = new int[M];

		for (int i = 0; i < M; i++) {
			A[i] = sc.nextInt()-1;
			B[i] = sc.nextInt()-1;
		}

		UnionFind uf=new UnionFind(N);

		int[] groupsize=new int[N];
		Arrays.fill(groupsize,1);


		for (int i = 0; i < M; i++) {

			if(uf.same(A[i], B[i])) {
				continue;
			}

			int BossA=uf.root(A[i]);
			int BossB=uf.root(B[i]);

			if(groupsize[BossA]<groupsize[BossB] ) {
				uf.par[BossA]=uf.root(BossB);

				groupsize[BossB]+=groupsize[BossA];


			}else if(groupsize[BossA]>groupsize[BossB]) {
				uf.par[uf.root(BossB)]=uf.root(BossA);

				groupsize[BossA]+=groupsize[BossB];

			}else {

				//番号が若いほど強いボス。
				if(BossA<BossB) {
					uf.par[BossB]=BossA;
					groupsize[BossA]+=groupsize[BossB];
				}else {
					uf.par[BossA]=BossB;
					groupsize[BossB]+=groupsize[BossA];
				}
			}
		}

		for (int i = 0; i < N; i++) {
			pln(uf.root(i)+1);
		}





	}

	public class UnionFind {

		int[] par;
		int[] rank;
		String commentYes = "Yes";
		String commentNO = "No";

		public UnionFind(int MaxN, String yes, String no) {
			par = new int[MaxN];
			rank = new int[MaxN];
			init(MaxN);

			commentYes = yes;
			commentNO = no;
		}

		public UnionFind(int MaxN) {
			par = new int[MaxN];
			rank = new int[MaxN];
			init(MaxN);
		}

		void recieveEdges(int M, Scanner sc, int indexed) {

			int diff = 0;

			if (indexed == 0) {
				diff = 1;
			}

			for (int i = 0; i < M; i++) {
				int A = sc.nextInt() - diff;
				int B = sc.nextInt() - diff;

				this.unite(A, B);
			}

		}

		//ｎ個の要素で初期化。
		void init(int n) {
			for (int i = 0; i < n; i++) {
				par[i] = i;
				rank[i] = 0;
			}
		}

		//木の根を求める
		public int root(int x) {

			//根までたどりついたので返させる。
			if (par[x] == x) {
				return x;
			} else {
				//経路圧縮
				return par[x] = root(par[x]);
			}

		}

		//xとyの根を比べて、同じ集合に属するかどうかを返す。
		public boolean same(int x, int y) {
			return root(x) == root(y);
		}

		//xとyの属する集合を併合
		public void unite(int x, int y) {
			x = root(x);
			y = root(y);

			if (x == y) {
				return;
			}

			if (rank[x] < rank[y]) {
				par[x] = y;
			} else {
				par[y] = x;

				if (rank[x] == rank[y]) {
					rank[x]++;
				}
			}
		}

		public void printJudge(int x, int y) {
			if (same(x, y)) {
				System.out.println(commentYes);
			} else {
				System.out.println(commentNO);
			}
		}

		//何本木があるか返させる。
		public int getNumOfSet() {
			Set<Integer> set = new TreeSet<Integer>();

			for (int i = 0; i < par.length; i++) {
				set.add(this.root(i));
			}

			return set.size();
		}

		public void changeComennt(String yes, String no) {
			commentYes = yes;
			commentNO = no;
		}
	}

	//以下テンプレート

	public static int[] extgcd(int a, int b) {

		int x0 = 1;
		int x1 = 0;

		int y0 = 0;
		int y1 = 1;

		while (b != 0) {
			int q = a / b;
			int r = a % b;

			int x2 = x0 - q * x1;
			int y2 = y0 - q * y1;

			a = b;
			b = r;

			x0 = x1;
			x1 = x2;

			y0 = y1;
			y1 = y2;
		}

		return new int[] { a, x0, y0 };

	}

	static int gcd(int a, int b) {

		if (b == 0)
			return a;

		if (a < b) {
			int t = a;
			a = b;
			b = t;
		}

		return gcd(b, a % b);

	}

	static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}

	static void swap(int[] a) {
		int t;

		t = a[0];
		a[0] = a[1];
		a[1] = t;

		return;
	}

	static <T> void output(List<T> list) {

		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i));

			if (i != list.size() - 1) {
				System.out.print(" ");
			} else {
				nl();
			}
		}

	}

	static void output(String[][] str) {

		for (int i = 0; i < str.length; i++) {
			for (int j = 0; j < str[i].length; j++) {
				print(str[i][j]);
			}

			nl();
		}

	}

	static void output(boolean flg, String Yes, String No) {

		if (flg) {
			pln(Yes);
		} else {
			pln(No);
		}

	}

	static void output(String[][] str, int digit) {

		String dig = "%" + String.valueOf(digit) + "s";

		for (int i = 0; i < str.length; i++) {
			for (int j = 0; j < str[i].length; j++) {
				System.out.printf(dig, str[i][j]);
			}
			nl();
		}

	}

	static void pln(String str) {
		System.out.println(str);
	}

	static void pln(int x) {
		System.out.println(x);
	}

	static void print(String str) {
		System.out.print(str);
	}

	static void print(int x) {
		System.out.print(x);
	}

	static void print(String str, int times) {
		for (int i = 0; i < times; i++) {
			print(str);
		}
	}

	static void print(int x, int times) {
		for (int i = 0; i < times; i++) {
			print(x);
		}
	}

	static void nl() {
		System.out.println();
	}

}
0