結果
問題 |
No.2290 UnUnion Find
|
ユーザー |
|
提出日時 | 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 |
ソースコード
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)]; } }