Cod sursa(job #2554639)

Utilizator TudorChirila11Tudor Chirila TudorChirila11 Data 23 februarie 2020 11:04:26
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define N 50005
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
typedef long long ll;
int n, m, i, j, g[N], x, y;
queue<int> q;
vector<int> v[N];
map<int,map<int,bool> > fr;
int main()
{
	fin>>n>>m;
	for(i=1;i<=m;++i)
	{
		fin>>x>>y;
		if(!fr[x][y])
		{
		v[x].pb(y);
		++g[y];
		fr[x][y]=1;
		}
	}
	for(i=1;i<=n;++i)
		if(!g[i])
			q.push(i);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		fout<<x<<' ';
		for(auto i:v[x])
		{
			--g[i];
			if(!g[i])
				q.push(i);
		}
	}
}