結果

問題 No.2290 UnUnion Find
ユーザー viral8
提出日時 2023-05-06 11:15:25
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,995 ms / 2,000 ms
コード長 1,098 bytes
コンパイル時間 3,215 ms
コンパイル使用メモリ 77,148 KB
実行使用メモリ 60,780 KB
最終ジャッジ日時 2024-11-23 20:32:07
合計ジャッジ時間 90,348 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Scanner;
import java.util.Arrays;
class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int Q = sc.nextInt();
		UnionFind uf = new UnionFind(N+1);
		while(Q-->0){
			int q = sc.nextInt();
			if(q==1){
				int u = sc.nextInt();
				int v = sc.nextInt();
				uf.unite(u,v);
			}
			else{
				int v = sc.nextInt();
				int ans = uf.unUnitePoint(v);
				if(ans>N)
					ans = -1;
				System.out.println(ans);
			}
		}
	}
}
class UnionFind{
	int[] par,unUnite;
	UnionFind(int N){
		par = new int[N];
		unUnite = new int[N];
		Arrays.fill(par,-1);
		Arrays.fill(unUnite,1);
		unUnite[1] = 2;
	}
	int root(int x){
		if(par[x]==-1)
			return x;
		return par[x] = root(par[x]);
	}
	void unite(int x,int y){
		int rootX = root(x);
		int rootY = root(y);
		if(rootX==rootY)
			return;
		par[rootY] = rootX;
		check(rootY);
		check(rootX);
	}
	void check(int x){
		int root = root(x);
		while(unUnite[root]<unUnite.length&&root==root(unUnite[root]))
			unUnite[root]++;
	}
	int unUnitePoint(int x){
		return unUnite[root(x)];
	}
}
0