結果
問題 | No.1865 Make Cycle |
ユーザー |
![]() |
提出日時 | 2022-03-04 22:02:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 264 ms / 3,000 ms |
コード長 | 1,054 bytes |
コンパイル時間 | 992 ms |
コンパイル使用メモリ | 75,224 KB |
最終ジャッジ日時 | 2025-01-28 05:19:31 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#include <iostream> #include <vector> using namespace std; vector<int> toposo(int n,vector<int> G[]){ int i; vector<int> t,in(n); for(i=0;i<n;i++){ for(int v:G[i]) in[v]++; } for(i=0;i<n;i++){ if(!in[i]) t.push_back(i); } i = 0; while(i<t.size()){ int u = t[i]; for(int v:G[u]){ in[v]--; if(in[v]==0) t.push_back(v); } i++; } return t; } vector<int> G[100010]; int a[100010],b[100010]; int main(){ int i,n,q; cin >> n >> q; for(i=0;i<q;i++){ cin >> a[i] >> b[i]; a[i]--; b[i]--; G[a[i]].push_back(b[i]); } vector<int> v = toposo(n,G); if(v.size()==n){ cout << -1 << endl; return 0; } int le = 0,ri = q - 1; while(ri - le>1){ int mid = (le + ri)/2; for(i=0;i<n;i++) G[i].clear(); for(i=0;i<=mid;i++) G[a[i]].push_back(b[i]); vector<int> v = toposo(n,G); if(v.size()<n) ri = mid; else le = mid; } cout << ri + 1 << endl; }