結果
問題 | No.2202 贅沢てりたまチキン |
ユーザー |
|
提出日時 | 2024-06-11 15:06:10 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,785 ms / 2,000 ms |
コード長 | 4,234 bytes |
コンパイル時間 | 4,145 ms |
コンパイル使用メモリ | 78,544 KB |
実行使用メモリ | 113,324 KB |
最終ジャッジ日時 | 2024-06-11 15:06:37 |
合計ジャッジ時間 | 24,101 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
import java.util.*;import java.lang.*;import java.io.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();UnionFindTree uft = new UnionFindTree(n*2);for (int j=0; j<m; j++) {int a = sc.nextInt()-1;int b = sc.nextInt()-1;uft.union(a , b + n);uft.union(b , a + n);}for (int j=0; j<n; j++) {if(!uft.same(j , j + n)){System.out.println("No");return;}}System.out.println("Yes");}}//Union find クラスclass UnionFindTree {int[] parent; // インデックスとノードを対応させ、そのルートノードのインデックスを格納int[] rank; // parentと同様に、木の高さを格納int[] size; // 木を構成する、要素の数を格納TreeSet<Integer> set = new TreeSet<>();int treeCount; // 木の数/*** コンストラクタ** @param n : 頂点の数*/public UnionFindTree(int n) {this.parent = new int[n];this.rank = new int[n];this.size = new int[n];this.treeCount = n;// 根を作る。for (int i = 0; i < n; i++) {makeSet(i);}}/*** 根をつくる。最初は、すべて異なる木に属しているものとする。** @param i : 頂点の数*/private void makeSet(int i) {parent[i] = i;rank[i] = 0; // 集合の高さsize[i] = 1; // 木を構成する要素の数set.add(i);}/*** 要素xが属する木と要素yが属する木を連結する。 木の高さ(ランク)を気にして、低い方に高い方をつなげる。(高い方の木を全体の木とする。)** @param x : 1つ目の要素(yとは異なる木に属している必要がある。)* @param y : 2つ目の要素(xとは異なる木に属している必要がある。)*/public void union(int x, int y) {int xRoot = find(x);int yRoot = find(y);int xSize = getSize(xRoot);int ySize = getSize(yRoot);// xが属する木の方が大きい場合if (rank[xRoot] > rank[yRoot]) {parent[yRoot] = xRoot; // yの親をxに更新size[xRoot] = xSize + ySize; // 木を構成する要素の数を更新treeCount--;set.remove(yRoot);} else if (rank[xRoot] < rank[yRoot]) {parent[xRoot] = yRoot;size[yRoot] = ySize + xSize;treeCount--;set.remove(xRoot);} else if (xRoot != yRoot) {parent[yRoot] = xRoot;rank[xRoot]++; // 同じ高さの木がルートの子として着くから大きさ++;size[xRoot] = xSize + ySize;treeCount--;set.remove(yRoot);}}/*** 要素の根を返す。 経路圧縮も同時に行う。(1→3→2となっていて2をfindした際、1→3,2と木の深さを浅くする。)** @param i* @return 要素iの根 (1→3→2となっていて2をfindした際、1となる。)*/public int find(int i) {if (i != parent[i]) {parent[i] = find(parent[i]);}return parent[i];}/*** 2つの要素が同じ木に属するかどうかを返す。** @param x : 1つ目の要素* @param y : 2つ目の要素* @return 同じ木に属していればtrue*/public boolean same(int x, int y) {return find(x) == find(y);}/*** 木の高さを返す。** @param i : 高さを調べたい木の根の番号* @return 木の高さ*/public int getRank(int i) {return rank[i];}/*** 木を構成する要素の数を返す。** @param i : 要素数を調べたい木の根の番号* @return 木を構成する要素の数*/public int getSize(int i) {return size[find(i)];}/*** 木の数を返す。** @return 木の数。*/public int getTreeCount() {return treeCount;}public int unUnion(int i){if(set.size() == 1){return -1;}int x = find(i);if(x == set.first()){return set.last();}return set.first();}}