結果
| 問題 | No.1805 Approaching Many Typhoon |
| ユーザー |
 kusagame12
|
| 提出日時 | 2024-06-12 16:10:45 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
AC
|
| 実行時間 | 228 ms / 2,000 ms |
| コード長 | 5,712 bytes |
| コンパイル時間 | 4,377 ms |
| コンパイル使用メモリ | 78,044 KB |
| 実行使用メモリ | 57,884 KB |
| 最終ジャッジ日時 | 2024-06-12 16:10:58 |
| 合計ジャッジ時間 | 9,936 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 123 ms
53,904 KB |
| testcase_01 | AC | 129 ms
53,888 KB |
| testcase_02 | AC | 128 ms
54,044 KB |
| testcase_03 | AC | 132 ms
53,508 KB |
| testcase_04 | AC | 115 ms
52,628 KB |
| testcase_05 | AC | 114 ms
52,936 KB |
| testcase_06 | AC | 125 ms
53,992 KB |
| testcase_07 | AC | 138 ms
54,088 KB |
| testcase_08 | AC | 130 ms
54,056 KB |
| testcase_09 | AC | 126 ms
53,912 KB |
| testcase_10 | AC | 118 ms
52,928 KB |
| testcase_11 | AC | 127 ms
53,972 KB |
| testcase_12 | AC | 125 ms
53,844 KB |
| testcase_13 | AC | 125 ms
53,920 KB |
| testcase_14 | AC | 128 ms
53,912 KB |
| testcase_15 | AC | 134 ms
53,880 KB |
| testcase_16 | AC | 133 ms
53,756 KB |
| testcase_17 | AC | 127 ms
53,776 KB |
| testcase_18 | AC | 131 ms
54,120 KB |
| testcase_19 | AC | 125 ms
53,948 KB |
| testcase_20 | AC | 105 ms
52,236 KB |
| testcase_21 | AC | 125 ms
53,736 KB |
| testcase_22 | AC | 128 ms
53,964 KB |
| testcase_23 | AC | 125 ms
53,756 KB |
| testcase_24 | AC | 130 ms
53,888 KB |
| testcase_25 | AC | 149 ms
53,828 KB |
| testcase_26 | AC | 125 ms
53,920 KB |
| testcase_27 | AC | 127 ms
53,708 KB |
| testcase_28 | AC | 206 ms
56,812 KB |
| testcase_29 | AC | 206 ms
56,876 KB |
| testcase_30 | AC | 210 ms
56,988 KB |
| testcase_31 | AC | 228 ms
57,884 KB |
| testcase_32 | AC | 162 ms
53,784 KB |
| testcase_33 | AC | 152 ms
53,792 KB |
| testcase_34 | AC | 184 ms
54,144 KB |
| testcase_35 | AC | 200 ms
56,452 KB |
| testcase_36 | AC | 197 ms
56,228 KB |
| testcase_37 | AC | 129 ms
53,716 KB |
| testcase_38 | AC | 142 ms
53,688 KB |
ソースコード
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();
int s = sc.nextInt()-1;
int g = sc.nextInt()-1;
List<Edge> edges = new ArrayList<>();
for (int i=0; i<m; i++) {
int f = sc.nextInt()-1;
int t = sc.nextInt()-1;
Edge edge = new Edge(f,t);
edges.add(edge);
}
int u = sc.nextInt();
int[] is = new int[u];
for (int k=0; k<u; k++) {
int i = sc.nextInt()-1;
is[k] = i;
}
List<Edge> canConnectEdges = new ArrayList<>();
for (Edge edge : edges) {
boolean connect = true;
for (int j=0; j<is.length; j++) {
int i = is[j];
if(edge.from == i || edge.to == i){
connect = false;
break;
}
}
if(connect){
canConnectEdges.add(edge);
}
}
UnionFindTree uft = new UnionFindTree(n);
for (Edge edge : canConnectEdges) {
int from = edge.from;
int to = edge.to;
uft.union(from,to);
}
System.out.println(uft.same(s,g) ? "Yes" : "No");
}
}
//Union find クラス
class UnionFindTree {
int[] parent; // インデックスとノードを対応させ、そのルートノードのインデックスを格納
int[] rank; // parentと同様に、木の高さを格納
int[] size; // 木を構成する、要素の数を格納
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; // 木を構成する要素の数
}
/**
* 要素xが属する木と要素yが属する木を連結する。 木の高さ（ランク）を気にして、低い方に高い方をつなげる。（高い方の木を全体の木とする。）
*
* @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; // yの親をxに更新
size[xRoot] = xSize + ySize; // 木を構成する要素の数を更新
treeCount--;
} else if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
size[yRoot] = ySize + xSize;
treeCount--;
} else if (xRoot != yRoot) {
parent[yRoot] = xRoot;
rank[xRoot]++; // 同じ高さの木がルートの子として着くから大きさ++;
size[xRoot] = xSize + ySize;
treeCount--;
}
}
/**
* 要素の根を返す。 経路圧縮も同時に行う。（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];
}
/**
* ２つの要素が同じ木に属するかどうかを返す。
*
* @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;
}
}
//グラフのエッジ(辺)を格納するクラス
class Edge
{
public final int from, to;
/**コンストラクタ
* @param : from 頂点
* @param : to つながっている頂点
*/
Edge(int from, int to)
{
this.from = from;
this.to = to;
}
}
//無向グラフクラス
class Graph
{
//隣接リストを表すリストのリスト(ある頂点が、どの頂点とつながっているかを保持するリスト)
List<List<Edge>> list = null;
/**コンストラクタ
* @param edges : 辺
* @param n : 頂点の個数
*
*/
Graph(List<Edge> edges, int n)
{
list = new ArrayList<>();
for (int i = 0; i < n; i++) {
list.add(new ArrayList<>());
}
//無向グラフにエッジを追加します
for (Edge edge: edges)
{
int from = edge.from;
int to = edge.to;
list.get(from).add(edge);
list.get(to).add(edge);
}
}
public int size() {
return list.size();
}
public List<Edge> getEdgsList(int vNum) {
return list.get(vNum);
}
}