Cod sursa(job #3001442)

Utilizator BadHero112Ursu Vasile BadHero112 Data 13 martie 2023 17:32:14
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=50001;
using namespace std;

int n,m;

vector<vector<int>> A(maxn,vector<int>());
int adj[maxn];

int main(){
	ifstream cin("sortaret.in");
	ofstream cout("sortaret.out");
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int c1,c2;
		cin>>c1>>c2;
		c1--;
		c2--;
		A[c1].push_back(c2);
		adj[c2]++;
	}
	queue<int> Q;
	vector<int> ord;
	for(int i=0;i<n;i++){
		if(adj[i]==0){
			Q.push(i);
			while(Q.size()){
				int i=Q.front();
				adj[i]--;
				ord.push_back(i);
				Q.pop();
				for(int j=0;j<A[i].size();j++){
					adj[A[i][j]]--;
					if(!adj[A[i][j]])Q.push(A[i][j]);
				}
			}
		}
	}
	for(int i=0;i<n;i++)cout<<ord[i]+1<<" ";
}