結果
問題 | No.2780 The Bottle Imp |
ユーザー |
![]() |
提出日時 | 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;}}