10011 | 2024-03-24 08:43:20 | 111 | Kritikus munkák | cpp17 | Accepted 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;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1824 KiB | ||||
2 | Accepted | 52ms | 13268 KiB | ||||
subtask2 | 25/25 | ||||||
3 | Accepted | 3ms | 2800 KiB | ||||
4 | Accepted | 3ms | 3112 KiB | ||||
5 | Accepted | 3ms | 3500 KiB | ||||
6 | Accepted | 3ms | 3392 KiB | ||||
7 | Accepted | 4ms | 3788 KiB | ||||
subtask3 | 25/25 | ||||||
8 | Accepted | 16ms | 5352 KiB | ||||
9 | Accepted | 8ms | 5004 KiB | ||||
10 | Accepted | 8ms | 5076 KiB | ||||
11 | Accepted | 12ms | 5392 KiB | ||||
12 | Accepted | 12ms | 5740 KiB | ||||
subtask4 | 25/25 | ||||||
13 | Accepted | 39ms | 12328 KiB | ||||
14 | Accepted | 41ms | 13268 KiB | ||||
15 | Accepted | 39ms | 13028 KiB | ||||
16 | Accepted | 39ms | 13228 KiB | ||||
17 | Accepted | 39ms | 13156 KiB | ||||
subtask5 | 25/25 | ||||||
18 | Accepted | 82ms | 21452 KiB | ||||
19 | Accepted | 79ms | 21472 KiB | ||||
20 | Accepted | 81ms | 21948 KiB | ||||
21 | Accepted | 79ms | 21736 KiB | ||||
22 | Accepted | 78ms | 21796 KiB |