結果

問題 No.2202 贅沢てりたまチキン
ユーザー kusagame12
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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);
}
/**
* xy
*
* @param x : (y)
* @param y : (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; // yx
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→22find1→3,2
*
* @param i
* @return i 1→3→22find1)
*/
public int find(int i) {
if (i != parent[i]) {
parent[i] = find(parent[i]);
}
return parent[i];
}
/**
*
*
* @param x :
* @param y :
* @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();
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0