Submission #1230920

#TimeUsernameProblemLanguageResultExecution timeMemory
1230920siewjhPovjerenstvo (COI22_povjerenstvo)C++20
100 / 100
276 ms59292 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
vector<int> adj[MAXN], radj[MAXN], ans;
int od[MAXN];
bool dd[MAXN];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int nodes, edges; cin >> nodes >> edges;
	for (int i = 0; i < edges; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); radj[b].push_back(a);
		od[a]++;
	}
	queue<int> q; int id = 1;
	for (int i = 1; i <= nodes; i++)
		if (od[i] == 0)
			q.push(i);
	while (id <= nodes){
		while (!q.empty()){
			int x = q.front(); q.pop();
			ans.push_back(x); dd[x] = 1;
			for (int px : radj[x]){
				if (dd[px]) continue;
				dd[px] = 1;
				for (int ppx : radj[px]){
					if (dd[ppx]) continue;
					od[ppx]--;
					if (od[ppx] == 0) q.push(ppx);
				}
			}
		}
		while (id <= nodes && dd[id]) id++;
		if (id <= nodes){
			ans.push_back(id); dd[id] = 1;
			vector<int> vx;
			for (int px : adj[id])
				if (!dd[px]){
					dd[px] = 1; vx.push_back(px);
				}
			for (int px : radj[id])
				if (!dd[px]){
					dd[px] = 1; vx.push_back(px);
				}
			for (int px : vx){
				for (int ppx : radj[px]){
					if (dd[ppx]) continue;
					od[ppx]--;
					if (od[ppx] == 0) q.push(ppx);
				}
			}
		}
	}
	cout << ans.size() << '\n';
	for (int x : ans) cout << x << ' ';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...