100112024-03-24 08:43:20111Kritikus munkákcpp17Elfogadva 100/10082ms21948 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1824 KiB
2Elfogadva52ms13268 KiB
subtask225/25
3Elfogadva3ms2800 KiB
4Elfogadva3ms3112 KiB
5Elfogadva3ms3500 KiB
6Elfogadva3ms3392 KiB
7Elfogadva4ms3788 KiB
subtask325/25
8Elfogadva16ms5352 KiB
9Elfogadva8ms5004 KiB
10Elfogadva8ms5076 KiB
11Elfogadva12ms5392 KiB
12Elfogadva12ms5740 KiB
subtask425/25
13Elfogadva39ms12328 KiB
14Elfogadva41ms13268 KiB
15Elfogadva39ms13028 KiB
16Elfogadva39ms13228 KiB
17Elfogadva39ms13156 KiB
subtask525/25
18Elfogadva82ms21452 KiB
19Elfogadva79ms21472 KiB
20Elfogadva81ms21948 KiB
21Elfogadva79ms21736 KiB
22Elfogadva78ms21796 KiB