10011 2024. 03. 24 08:43:20 111 Kritikus munkák cpp17 Elfogadva 100/100 82ms 21948 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	vector<vector<int>>g(N+2);
	vector<int>c(N+2);
	for(int i=0;i<M;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		c[b]++;
	}
	for(int i=1;i<=N;i++){
		if(c[i]==0&&g[i].size()>0){
			g[0].push_back(i);
		}
		if(c[i]>0&&g[i].size()==0){
			g[i].push_back(N+1);
		}
	}
	vector<int>a(N+2);
	vector<int>p;
	int s=0;
	while(true){
		p.push_back(s);
		a[s]=p.size();
		int z=0;
		for(int i:g[s]){
			if(!a[i]){
				z=i;
				break;
			}
		}
		if(!z){
			break;
		}
		s=z;
	}
	int h=0;
	auto dfs=[&](auto self,int i)->void{
		if(a[i]){
			h=max(h,a[i]);
			return;
		}
		a[i]=-1;
		for(int j:g[i]){
			self(self,j);
		}
	};
	for(int i:p){
		if(h>a[i]){
			a[i]=-1;
		}
		for(int j:g[i]){
			dfs(dfs,j);
		}
	}
	vector<int>ans;
	for(int i=1;i<=N;i++){
		if(a[i]>0){
			ans.push_back(i);
		}
	}
	cout<<ans.size()<<'\n';
	for(int i:ans){
		cout<<i<<' ';
	}
	cout<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1824 KiB
2 Elfogadva 52ms 13268 KiB
subtask2 25/25
3 Elfogadva 3ms 2800 KiB
4 Elfogadva 3ms 3112 KiB
5 Elfogadva 3ms 3500 KiB
6 Elfogadva 3ms 3392 KiB
7 Elfogadva 4ms 3788 KiB
subtask3 25/25
8 Elfogadva 16ms 5352 KiB
9 Elfogadva 8ms 5004 KiB
10 Elfogadva 8ms 5076 KiB
11 Elfogadva 12ms 5392 KiB
12 Elfogadva 12ms 5740 KiB
subtask4 25/25
13 Elfogadva 39ms 12328 KiB
14 Elfogadva 41ms 13268 KiB
15 Elfogadva 39ms 13028 KiB
16 Elfogadva 39ms 13228 KiB
17 Elfogadva 39ms 13156 KiB
subtask5 25/25
18 Elfogadva 82ms 21452 KiB
19 Elfogadva 79ms 21472 KiB
20 Elfogadva 81ms 21948 KiB
21 Elfogadva 79ms 21736 KiB
22 Elfogadva 78ms 21796 KiB