結果
問題 | No.1553 Lovely City |
ユーザー |
![]() |
提出日時 | 2021-07-29 08:02:25 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,169 ms / 2,000 ms |
コード長 | 6,594 bytes |
コンパイル時間 | 2,701 ms |
コンパイル使用メモリ | 85,240 KB |
実行使用メモリ | 113,016 KB |
最終ジャッジ日時 | 2024-09-14 05:38:25 |
合計ジャッジ時間 | 27,810 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.math.BigDecimal;import java.math.RoundingMode;import java.util.*;import java.io.File;import java.io.FileDescriptor;import java.io.FileOutputStream;import java.io.OutputStream;import java.io.UncheckedIOException;import java.lang.reflect.Field;import java.nio.CharBuffer;import java.nio.charset.CharacterCodingException;import java.nio.charset.CharsetEncoder;import java.nio.charset.StandardCharsets;public class Main {static final long MOD=1000000007;static final long MOD1=998244353;static int ans=0;public static void main(String[] args){PrintWriter out = new PrintWriter(System.out);InputReader sc=new InputReader(System.in);int N = sc.nextInt();int M = sc.nextInt();int ans = 0;ArrayList<Integer>[] E = new ArrayList[N];for (int i = 0; i < E.length; i++) {E[i] = new ArrayList<>();}UnionFindTree uTree = new UnionFindTree(N);int[] deg = new int[N];for (int i = 0; i < M; i++) {int a = sc.nextInt()-1;int b = sc.nextInt()-1;deg[b]++;uTree.union(a, b, 1);E[a].add(b);}ArrayList<Integer>[] group = new ArrayList[N];for (int i = 0; i < group.length; i++) {group[i] = new ArrayList<>();}for (int i = 0; i < N; i++) {group[uTree.find(i)].add(i);}ArrayList<String> anStrings = new ArrayList<>();for (int i = 0; i < group.length; i++) {if(group[i].size()<=1)continue;ArrayDeque<Integer> deq = new ArrayDeque<>();ArrayList<Integer> topo = new ArrayList<>();for (int v: group[i]) {if(deg[v]==0)deq.add(v);}int c = 0;while (!deq.isEmpty()) {int v = deq.pollFirst();topo.add(v);c++;for (Integer to: E[v]) {deg[to]--;if (deg[to]==0) {deq.add(to);}}}if (c==group[i].size()) {for (int j = 0; j < topo.size()-1; j++) {anStrings.add((topo.get(j)+1)+" "+(topo.get(j+1)+1));}ans += group[i].size()-1;}else {ans += group[i].size();int size = group[i].size();for (int j = 0; j < group[i].size(); j++) {int from = group[i].get((j-1+size)%size)+1;int to = group[i].get(j%size)+1;anStrings.add(from+" "+to);}}}out.println(ans);for (String string : anStrings) {out.println(string);}out.flush();}static class UnionFindTree{int[] par;int[] rank;int[] size;int[] diff_weight;int arraysize;public UnionFindTree(int n) {this.par=new int[n];this.rank=new int[n];this.size=new int[n];this.diff_weight=new int[n];arraysize=n;for (int i = 0; i < arraysize; i++) {set(i);}}public void set(int i) {par[i]=i;rank[i]=0;size[i]=1;diff_weight[i]=0;}public void union(int x,int y,int w) {w += weight(x);w -= weight(y);int rootx=find(x);int rooty=find(y);if (rootx==rooty) {return;}if (rank[rootx]>rank[rooty]) {par[rooty]=rootx;diff_weight[rooty] = w;size[rootx]+=size[rooty];}else if (rank[rootx]<rank[rooty]) {par[rootx]=rooty;w=-w;diff_weight[rootx] = w;size[rooty]+=size[rootx];}else {par[rooty]=rootx;diff_weight[rooty] = w;rank[rootx]++;size[rootx]+=size[rooty];}}public int find(int x) {if(par[x] == x) return x;int r = find(par[x]);diff_weight[x] += diff_weight[par[x]];return par[x] = r;}public int weight(int x) {find(x);return diff_weight[x];}public int size(int i) {return size[find(i)];}public int diff(int x, int y) {return weight(y) - weight(x);}public boolean same(int x, int y) {return find(x) == find(y);}}static class InputReader {private InputStream in;private byte[] buffer = new byte[1024];private int curbuf;private int lenbuf;public InputReader(InputStream in) {this.in = in;this.curbuf = this.lenbuf = 0;}public boolean hasNextByte() {if (curbuf >= lenbuf) {curbuf = 0;try {lenbuf = in.read(buffer);} catch (IOException e) {throw new InputMismatchException();}if (lenbuf <= 0)return false;}return true;}private int readByte() {if (hasNextByte())return buffer[curbuf++];elsereturn -1;}private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}private void skip() {while (hasNextByte() && isSpaceChar(buffer[curbuf]))curbuf++;}public boolean hasNext() {skip();return hasNextByte();}public String next() {if (!hasNext())throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (!isSpaceChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public int nextInt() {if (!hasNext())throw new NoSuchElementException();int c = readByte();while (isSpaceChar(c))c = readByte();boolean minus = false;if (c == '-') {minus = true;c = readByte();}int res = 0;do {if (c < '0' || c > '9')throw new InputMismatchException();res = res * 10 + c - '0';c = readByte();} while (!isSpaceChar(c));return (minus) ? -res : res;}public long nextLong() {if (!hasNext())throw new NoSuchElementException();int c = readByte();while (isSpaceChar(c))c = readByte();boolean minus = false;if (c == '-') {minus = true;c = readByte();}long res = 0;do {if (c < '0' || c > '9')throw new InputMismatchException();res = res * 10 + c - '0';c = readByte();} while (!isSpaceChar(c));return (minus) ? -res : res;}public double nextDouble() {return Double.parseDouble(next());}public int[] nextIntArray(int n) {int[] a = new int[n];for (int i = 0; i < n; i++)a[i] = nextInt();return a;}public double[] nextDoubleArray(int n) {double[] a = new double[n];for (int i = 0; i < n; i++)a[i] = nextDouble();return a;}public long[] nextLongArray(int n) {long[] a = new long[n];for (int i = 0; i < n; i++)a[i] = nextLong();return a;}public char[][] nextCharMap(int n, int m) {char[][] map = new char[n][m];for (int i = 0; i < n; i++)map[i] = next().toCharArray();return map;}}}