# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
789058 | Username4132 | Povjerenstvo (COI22_povjerenstvo) | C++14 | 402 ms | 101108 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define PB push_back
const int MAXN = 500010;
int n, m, cn;
bool vis[MAXN], ans[MAXN], del[MAXN];
vector<int> g[MAXN], gi[MAXN], order, toDel;
void dfs1(int v){
vis[v]=true;
for(int to:gi[v]) if(!vis[to]) dfs1(to);
order.PB(v);
}
void dfs2(int v, bool flag){
del[v]=true;
if(flag){
ans[v]=true;
for(int to:gi[v]) toDel.PB(to);
}
for(int to:g[v]) if(!del[to]) dfs2(to, !flag);
}
int main(){
scanf("%d %d", &n, &m);
forn(i, m){
int a, b; scanf("%d %d", &a, &b); --a, --b;
g[a].PB(b), gi[b].PB(a);
}
forn(i, n) if(!vis[i]) dfs1(i);
reverse(order.begin(), order.end());
for(int el:order) if(!del[el]){
dfs2(el, true);
for(int de:toDel) del[de]=true;
toDel.clear();
}
forn(i, n) cn+=ans[i];
printf("%d\n", cn);
forn(i, n) if(ans[i]) printf("%d ", i+1);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |