Cod sursa(job #2778198)

Utilizator DariusM07Darius Feher DariusM07 Data 30 septembrie 2021 01:12:35
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

const int maxN = 50001;
vector <int> Adj[maxN];
bool hasParent[maxN];
bool visited[maxN];

void bfs(vector<int> Adj[]) {
	queue <int> nodes;
	nodes.push(0);

	while(!nodes.empty()) {
		int front = nodes.front();
		nodes.pop();
		int n = Adj[front].size();
		for (int i = 0; i < n; ++i) {
			if (!visited[Adj[front][i]]) {
				visited[Adj[front][i]] = true;
				g << Adj[front][i] << " ";
				nodes.push(Adj[front][i]);
			}
		}
	}
}

int main() {
	int n, m;
	f >> n >> m;
	int i, j;
	for (int t = 1; t <= m; ++t) {
		f >> i >> j;
		hasParent[j] = true;
		Adj[i].push_back(j);
	}
	for (int i = 1; i <= n; ++i) {
		if (!hasParent[i]) {
			Adj[0].push_back(i);
		}
	}
	bfs(Adj);
	f.close();
	g.close();
	return 0;
}