結果
| 問題 |
No.1865 Make Cycle
|
| コンテスト | |
| ユーザー |
 shojin_pro
|
| 提出日時 | 2022-03-04 23:56:00 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 979 ms / 3,000 ms |
| コード長 | 8,401 bytes |
| コンパイル時間 | 3,428 ms |
| コンパイル使用メモリ | 81,556 KB |
| 実行使用メモリ | 79,156 KB |
| 最終ジャッジ日時 | 2024-07-18 22:52:06 |
| 合計ジャッジ時間 | 21,485 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 20 |
ソースコード
import java.util.*;
import java.io.*;
public class Main {
static FastScanner sc = new FastScanner(System.in);
static PrintWriter pw = new PrintWriter(System.out);
static StringBuilder sb = new StringBuilder();
static long mod = (long) 1e9 + 7;
public static void main(String[] args) throws Exception {
solve();
pw.flush();
}
public static void solve() {
int N = sc.nextInt();
int Q = sc.nextInt();
ArrayList<int[]> arr = new ArrayList<>();
for(int i = 0; i < Q; i++){
arr.add(new int[]{sc.nextInt()-1,sc.nextInt()-1});
}
int left = 1;
int right = Q+1;
boolean ok = false;
while(right - left > 1){
SCC scc = new SCC(N);
int mid = (right+left)/2;
for(int i = 0; i < mid; i++){
scc.addEdge(arr.get(i)[0],arr.get(i)[1]);
}
int[][] dp = scc.build();
if(dp.length != N){
right = mid;
ok = true;
}else{
left = mid;
}
}
pw.println(ok ? right : -1);
}
static class GeekInteger {
public static void save_sort(int[] array) {
shuffle(array);
Arrays.sort(array);
}
public static int[] shuffle(int[] array) {
int n = array.length;
Random random = new Random();
for (int i = 0, j; i < n; i++) {
j = i + random.nextInt(n - i);
int randomElement = array[j];
array[j] = array[i];
array[i] = randomElement;
}
return array;
}
public static void save_sort(long[] array) {
shuffle(array);
Arrays.sort(array);
}
public static long[] shuffle(long[] array) {
int n = array.length;
Random random = new Random();
for (int i = 0, j; i < n; i++) {
j = i + random.nextInt(n - i);
long randomElement = array[j];
array[j] = array[i];
array[i] = randomElement;
}
return array;
}
}
}
/**
* @verified https://atcoder.jp/contests/practice2/tasks/practice2_g
*/
class SCC {
static class Edge {
int from, to;
public Edge(int from, int to) {
this.from = from; this.to = to;
}
}
final int n;
int m;
final java.util.ArrayList<Edge> unorderedEdges;
final int[] start;
final int[] ids;
boolean hasBuilt = false;
public SCC(int n) {
this.n = n;
this.unorderedEdges = new java.util.ArrayList<>();
this.start = new int[n + 1];
this.ids = new int[n];
}
public void addEdge(int from, int to) {
rangeCheck(from);
rangeCheck(to);
unorderedEdges.add(new Edge(from, to));
start[from + 1]++;
this.m++;
}
public int id(int i) {
if (!hasBuilt) {
throw new UnsupportedOperationException(
"Graph hasn't been built."
);
}
rangeCheck(i);
return ids[i];
}
public int[][] build() {
for (int i = 1; i <= n; i++) {
start[i] += start[i - 1];
}
Edge[] orderedEdges = new Edge[m];
int[] count = new int[n + 1];
System.arraycopy(start, 0, count, 0, n + 1);
for (Edge e : unorderedEdges) {
orderedEdges[count[e.from]++] = e;
}
int nowOrd = 0;
int groupNum = 0;
int k = 0;
// parent
int[] par = new int[n];
int[] vis = new int[n];
int[] low = new int[n];
int[] ord = new int[n];
java.util.Arrays.fill(ord, -1);
// u = lower32(stack[i]) : visiting vertex
// j = upper32(stack[i]) : jth child
long[] stack = new long[n];
// size of stack
int ptr = 0;
// non-recursional DFS
for (int i = 0; i < n; i++) {
if (ord[i] >= 0) continue;
par[i] = -1;
// vertex i, 0th child.
stack[ptr++] = 0l << 32 | i;
// stack is not empty
while (ptr > 0) {
// last element
long p = stack[--ptr];
// vertex
int u = (int) (p & 0xffff_ffffl);
// jth child
int j = (int) (p >>> 32);
if (j == 0) { // first visit
low[u] = ord[u] = nowOrd++;
vis[k++] = u;
}
if (start[u] + j < count[u]) { // there are more children
// jth child
int to = orderedEdges[start[u] + j].to;
// incr children counter
stack[ptr++] += 1l << 32;
if (ord[to] == -1) { // new vertex
stack[ptr++] = 0l << 32 | to;
par[to] = u;
} else { // backward edge
low[u] = Math.min(low[u], ord[to]);
}
} else { // no more children (leaving)
while (j --> 0) {
int to = orderedEdges[start[u] + j].to;
// update lowlink
if (par[to] == u) low[u] = Math.min(low[u], low[to]);
}
if (low[u] == ord[u]) { // root of a component
while (true) { // gathering verticies
int v = vis[--k];
ord[v] = n;
ids[v] = groupNum;
if (v == u) break;
}
groupNum++; // incr the number of components
}
}
}
}
for (int i = 0; i < n; i++) {
ids[i] = groupNum - 1 - ids[i];
}
int[] counts = new int[groupNum];
for (int x : ids) 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 cmp = ids[i];
groups[cmp][--counts[cmp]] = i;
}
hasBuilt = true;
return groups;
}
private void rangeCheck(int i) {
if (i < 0 || i >= n) {
throw new IndexOutOfBoundsException(
String.format("Index %d out of bounds for length %d", i, n)
);
}
}
}
class FastScanner {
private BufferedReader reader = null;
private StringTokenizer tokenizer = null;
public FastScanner(InputStream in) {
reader = new BufferedReader(new InputStreamReader(in));
tokenizer = null;
}
public FastScanner(FileReader in) {
reader = new BufferedReader(in);
tokenizer = null;
}
public String next() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public String nextLine() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
return reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken("\n");
}
public long nextLong() {
return Long.parseLong(next());
}
public int nextInt() {
return Integer.parseInt(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
public String[] nextArray(int n) {
String[] a = new String[n];
for (int i = 0; i < n; i++)
a[i] = next();
return a;
}
public int[] nextIntArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
public long[] nextLongArray(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
}