結果

問題 No.1865 Make Cycle
ユーザー しゅらにるーとに
提出日時 2025-10-05 20:08:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 379 ms / 3,000 ms
コード長 1,292 bytes
コンパイル時間 3,114 ms
コンパイル使用メモリ 223,540 KB
実行使用メモリ 9,808 KB
最終ジャッジ日時 2025-10-05 20:08:13
合計ジャッジ時間 10,666 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll=long long;
using ul=unsigned long long;
using ld=long double;
using mint = modint1000000007;
int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};
using Graph=vector<vector<int>>;
vector<int>TopologicalSort(const vector<vector<int>>& graph){
	vector<int> indegrees(graph.size());
	for(const auto& v:graph){
		for(const auto& to:v)indegrees[to]++;
	}
	//辞書順最大 → greater<int>を消す
	priority_queue<int,vector<int>,greater<int>>pq;
	for(int i=0;i<(int)graph.size();i++){
		if(indegrees[i]==0)pq.push(i);
	}
	vector<int> result;
	while (!pq.empty()){
		const int from=pq.top();pq.pop();
		result.push_back(from);
		for (const auto& to:graph[from]){
			if(--indegrees[to]==0)pq.push(to);
		}
	}
	if(result.size()!=graph.size())return{};
	return result;
}
int main(){
    int N,Q;
    cin>>N>>Q;
    vector<int>A(Q),B(Q);
    for(int i=0;i<Q;i++)cin>>A[i]>>B[i],A[i]--,B[i]--;
    int l=0,r=Q+1;
    while(r-l>1){
    	vector<vector<int>>G(N);
    	int m=(l+r)/2;
    	for(int i=0;i<m;i++)G[A[i]].push_back(B[i]);
    	vector<int>T=TopologicalSort(G);
    	if(T.size()==0)r=m;
    	else l=m;
    }
    if(l==Q)cout<<-1<<endl;
    else cout<<l+1<<endl;
}
0