Cod sursa(job #2973906)

Utilizator lukaszisgabiManoliu Gabriel lukaszisgabi Data 2 februarie 2023 19:40:14
Problema Sortare topologica Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<iostream>
#include<vector>
using namespace std;

#define fileIn "sortaret.in"
#define fileOut "sortaret.out"
#define nul nullptr

#define MAX_N 100000
#define MAX_M 400000

int n, m, in[MAX_N + 1], fin[MAX_N + 1], k;
bool viz[MAX_N + 1];

vector<int> V[MAX_N+1];

void citire() {
	ifstream fin(fileIn);
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int v1, v2;
		fin >> v1 >> v2;
		V[v1].push_back(v2);
		in[v2]++;
	}
	fin.close();
}

void parcurgere() {
	int x = n;
	while (x && k < n) {
		if (in[x] == 0 && !viz[x]) {
			
			for (auto i : V[x]) {
				in[i]--;
			}

			viz[x] = 1;
			fin[++k] = x;
			x = n;
		}
		else x--;
	}
}

void afisare() {
	ofstream fout(fileOut);
	for (int i = 1; i <= n; i++) fout << fin[i] << ' ';
	fout.close();
}

int main() {
	citire();
	parcurgere();
	afisare();
	return 0;
}