100102024-03-24 08:26:55111Kritikus munkákcpp17Wrong answer 0/10083ms42676 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+1);
	vector<int>c(N+1);
	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[0].push_back(i);
		}
	}
	vector<int>a(N+1);
	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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1828 KiB
2Accepted52ms14508 KiB
subtask20/25
3Wrong answer3ms3932 KiB
4Accepted3ms4308 KiB
5Accepted3ms4444 KiB
6Accepted3ms4388 KiB
7Wrong answer4ms4712 KiB
subtask30/25
8Wrong answer14ms6736 KiB
9Wrong answer8ms6432 KiB
10Wrong answer8ms6512 KiB
11Wrong answer12ms7476 KiB
12Wrong answer10ms7672 KiB
subtask40/25
13Wrong answer41ms15048 KiB
14Accepted39ms17476 KiB
15Accepted39ms18672 KiB
16Accepted39ms20284 KiB
17Accepted37ms21428 KiB
subtask50/25
18Accepted79ms32512 KiB
19Wrong answer79ms35176 KiB
20Wrong answer83ms38152 KiB
21Wrong answer79ms40548 KiB
22Wrong answer79ms42676 KiB