結果
| 問題 | No.2780 The Bottle Imp |
| コンテスト | |
| ユーザー |
 ks2m
|
| 提出日時 | 2024-06-07 22:10:26 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,047 bytes |
| 記録 | |
| コンパイル時間 | 7,800 ms |
| コンパイル使用メモリ | 84,376 KB |
| 実行使用メモリ | 98,884 KB |
| 最終ジャッジ日時 | 2024-12-27 13:50:06 |
| 合計ジャッジ時間 | 16,937 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 39 WA * 1 |
ソースコード
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
static List<Set<Integer>> list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] m = new int[n];
int[][] a = new int[n][];
for (int i = 0; i < n; i++) {
String[] sa = br.readLine().split(" ");
m[i] = Integer.parseInt(sa[0]);
a[i] = new int[m[i]];
for (int j = 0; j < m[i]; j++) {
a[i][j] = Integer.parseInt(sa[j + 1]) - 1;
}
}
br.close();
SCC scc = new SCC(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m[i]; j++) {
scc.addEdge(i, a[i][j]);
}
}
int[][] g = scc.scc();
DSU uf = new DSU(n);
for (int i = 0; i < g.length; i++) {
for (int j = 1; j < g[i].length; j++) {
uf.merge(g[i][0], g[i][j]);
}
}
list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(new HashSet<>());
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m[i]; j++) {
if (!uf.same(i, a[i][j])) {
list.get(uf.leader(i)).add(uf.leader(a[i][j]));
}
}
}
boolean[] vis = new boolean[n];
boolean res = dfs(uf.leader(0), vis);
if (!res) {
System.out.println("No");
return;
}
for (int i = 0; i < n; i++) {
if (!vis[uf.leader(i)]) {
System.out.println("No");
return;
}
}
System.out.println("Yes");
}
static boolean dfs(int x, boolean[] vis) {
vis[x] = true;
Set<Integer> nexts = list.get(x);
if (nexts.size() > 1) {
return false;
}
if (nexts.isEmpty()) {
return true;
}
return dfs(nexts.iterator().next(), vis);
}
}
class SCC {
/** gid[i]：頂点iが何番目の強連結成分に属しているか */
int[] gid;
private final int n;
private List<Edge> edges;
private int nowOrd, groupNum;
private int[] start, low, ord;
private Edge[] elist;
private Deque<Integer> visited;
private class Edge {
final int from, to;
public Edge(int from, int to) {
this.from = from;
this.to = to;
}
}
/**
* n頂点0辺のグラフを作る。<br>
* O(n)
*
* @param n 頂点数
*/
public SCC(int n) {
this.n = n;
edges = new ArrayList<>();
}
/**
* fromからtoへ有向辺を追加する。<br>
* ならしO(1)
*
* @param from 有向辺の始点（0≦from＜n）
* @param to 有向辺の終点（0≦to＜n）
*/
void addEdge(int from, int to) {
assert 0 <= from && from < n : "from=" + from;
assert 0 <= to && to < n : "to=" + to;
edges.add(new Edge(from, to));
}
/**
* <pre>
* 強連結成分分解
* 辺の本数をmとして、O(n + m)
*
* ・全ての頂点がちょうど1つずつ、内側の配列のどれかに含まれる。
* ・内側の配列（1つの強連結成分）内での頂点の順序は未定義。
* ・外側の配列はトポロジカルソートされている。
* </pre>
*
* @return 強連結成分ごとの頂点の配列
*/
int[][] scc() {
start = new int[n + 1];
for (Edge e : edges) {
start[e.from + 1]++;
}
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
elist = new Edge[edges.size()];
int[] counter = Arrays.copyOf(start, n + 1);
for (Edge e : edges) {
elist[counter[e.from]++] = e;
}
nowOrd = 0;
groupNum = 0;
visited = new ArrayDeque<>();
low = new int[n];
ord = new int[n];
gid = new int[n];
Arrays.fill(ord, -1);
for (int i = 0; i < n; i++) {
if (ord[i] == -1) {
dfs(i);
}
}
for (int i = 0; i < n; i++) {
gid[i] = groupNum - 1 - gid[i];
}
int[] counts = new int[groupNum];
for (int x : gid) {
counts[x]++;
}
int[][] groups = new int[groupNum][];
for (int i = 0; i < groupNum; i++) {
groups[i] = new int[counts[i]];
}
for (int i = 0; i < n; i++) {
int idx = gid[i];
groups[idx][--counts[idx]] = i;
}
return groups;
}
private void dfs(int v) {
low[v] = ord[v] = nowOrd++;
visited.add(v);
for (int i = start[v]; i < start[v + 1]; i++) {
int to = elist[i].to;
if (ord[to] == -1) {
dfs(to);
low[v] = Math.min(low[v], low[to]);
} else {
low[v] = Math.min(low[v], ord[to]);
}
}
if (low[v] == ord[v]) {
while (true) {
int u = visited.pollLast();
ord[u] = n;
gid[u] = groupNum;
if (u == v) {
break;
}
}
groupNum++;
}
}
}
class DSU {
private int n;
private int[] parentOrSize;
private int num;
/**
* n頂点0辺の無向グラフを作る。<br>
* O(n)
*
* @param n 頂点数
*/
public DSU(int n) {
this.n = n;
this.parentOrSize = new int[n];
Arrays.fill(parentOrSize, -1);
num = n;
}
/**
* 辺(a, b)を足す。<br>
* ならしO(α(n))
*
* @param a 頂点番号（0≦a＜n）
* @param b 頂点番号（0≦b＜n）
* @return 代表元
*/
int merge(int a, int b) {
assert 0 <= a && a < n : "a=" + a;
assert 0 <= b && b < n : "b=" + b;
int x = leader(a);
int y = leader(b);
if (x == y) {
return x;
}
if (-parentOrSize[x] < -parentOrSize[y]) {
int tmp = x;
x = y;
y = tmp;
}
parentOrSize[x] += parentOrSize[y];
parentOrSize[y] = x;
num--;
return x;
}
/**
* 頂点a, bが連結かどうか。<br>
* ならしO(α(n))
*
* @param a 頂点番号（0≦a＜n）
* @param b 頂点番号（0≦b＜n）
* @return true：連結 false：非連結
*/
boolean same(int a, int b) {
assert 0 <= a && a < n : "a=" + a;
assert 0 <= b && b < n : "b=" + b;
return leader(a) == leader(b);
}
/**
* 頂点aの属する連結成分の代表元を返す。<br>
* ならしO(α(n))
*
* @param a 頂点番号（0≦a＜n）
* @return 代表元
*/
int leader(int a) {
assert 0 <= a && a < n : "a=" + a;
if (parentOrSize[a] < 0) {
return a;
} else {
return parentOrSize[a] = leader(parentOrSize[a]);
}
}
/**
* 頂点aの属する連結成分の要素数を返す。<br>
* ならしO(α(n))
*
* @param a 頂点番号（0≦a＜n）
* @return 要素数
*/
int size(int a) {
assert 0 <= a && a < n : "a=" + a;
return -parentOrSize[leader(a)];
}
/**
* 連結成分の数を返す。<br>
* O(1)
*
* @return 連結成分数
*/
int num() {
return num;
}
/**
* グラフを連結成分に分けた情報を返す。<br>
* O(n)
*
* @return 「1つの連結成分の頂点番号のリスト」のリスト
*/
List<List<Integer>> groups() {
int[] leaderBuf = new int[n];
int[] groupSize = new int[n];
for (int i = 0; i < n; i++) {
leaderBuf[i] = leader(i);
groupSize[leaderBuf[i]]++;
}
List<List<Integer>> result = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
result.add(new ArrayList<>(groupSize[i]));
}
for (int i = 0; i < n; i++) {
result.get(leaderBuf[i]).add(i);
}
result.removeIf(List::isEmpty);
return result;
}
}