Cod sursa(job #2667745)

Utilizator zaBogdanZavadovschi Bogdan zaBogdan Data 3 noiembrie 2020 19:52:33
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int maxNr = 1e6+10;
bool viz[maxNr];
vector<int> v[maxNr];
int gradInt[maxNr];

int main(){
	int n,m;
	ifstream f("sortaret.in");
	f >> n >> m;
	for(int i=0;i<m;i++){
		int x,y;
		f >> x>> y;
		v[x].push_back(y);
		gradInt[y]++;
	}
	f.close();
	queue<int> q;
	list<int> l;
	for(int i=1;i<=n;i++)
		if(gradInt[i]==0){
			viz[i]=1;
			q.push(i);
			for(auto ii: v[i])
				gradInt[ii]--;
		}
	while(!q.empty()){
		int nod = q.front();
		l.push_back(nod);
		q.pop();
		for(auto it: v[nod]){
			if(!gradInt[it] && !viz[it]){
				viz[it]=1;
				q.push(it);
				for(auto ii: v[it])
					gradInt[ii]--;
			}
		}
	}
	ofstream g("sortaret.out");
	for(auto it: l)
		cout << it << ' ';
	g.close();
    //linux output debug.
    cout << '\n';
    return 0;
}