10010 2024. 03. 24 08:26:55 111 Kritikus munkák cpp17 Hibás válasz 0/100 83ms 42676 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Elfogadva 52ms 14508 KiB
subtask2 0/25
3 Hibás válasz 3ms 3932 KiB
4 Elfogadva 3ms 4308 KiB
5 Elfogadva 3ms 4444 KiB
6 Elfogadva 3ms 4388 KiB
7 Hibás válasz 4ms 4712 KiB
subtask3 0/25
8 Hibás válasz 14ms 6736 KiB
9 Hibás válasz 8ms 6432 KiB
10 Hibás válasz 8ms 6512 KiB
11 Hibás válasz 12ms 7476 KiB
12 Hibás válasz 10ms 7672 KiB
subtask4 0/25
13 Hibás válasz 41ms 15048 KiB
14 Elfogadva 39ms 17476 KiB
15 Elfogadva 39ms 18672 KiB
16 Elfogadva 39ms 20284 KiB
17 Elfogadva 37ms 21428 KiB
subtask5 0/25
18 Elfogadva 79ms 32512 KiB
19 Hibás válasz 79ms 35176 KiB
20 Hibás válasz 83ms 38152 KiB
21 Hibás válasz 79ms 40548 KiB
22 Hibás válasz 79ms 42676 KiB