Cod sursa(job #3032018)

Utilizator tudor036Borca Tudor tudor036 Data 21 martie 2023 12:20:24
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream F("sortaret.in");
ofstream G("sortaret.out");

vector<vector<int>> list;
vector<int> ans;
int N, M;

void Read() {
	int x, y;

	F >> N >> M;

	list.resize(N + 1);

	while (M--) {
		F >> x >> y;
		list[x].push_back(y);
	}

	F.close();
}

void DFS(int s, vector<int> &u) {
	stack<int> st;
	int c;

	st.push(s);

	while (!st.empty()) {
		c = st.top();
		st.pop();

		if (!u[c]) {
			u[c] = 1;

			for (int v : list[c]) {
				st.push(v);
			}

			ans.push_back(c);
		}
	}
}

void Solve() {
	vector<int> used(N + 1, 0);
	for(size_t i = 1; i <= N; i++) {
		if (!used[i]) {
			DFS(i, used);
		}
	}
}

void Print() {
	for (size_t indx = 0; indx < ans.size(); indx++) {
		G << ans[indx] << " ";
	}
	
	G.close();
}

int main()
{
	Read();
	Solve();
	Print();

	return 0;
}