Cod sursa(job #2711316)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 23 februarie 2021 22:11:16
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;

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

struct node{
	int val;
	node *next;
};

node *gr[50001];
node *answ;

bitset <50001> marked;

int n, m, x, y;

void push(node *&t, int x){
	node *p = new node;
	p -> val = x;
	p -> next = t;
	t = p;
}

void add(int y){
	node *p = new node;
	p -> val = y;
	p -> next = gr[x];
	gr[x] = p;
}

void dfs(int k){
	marked[k] = 1;
	while(gr[k] != NULL){
		int to = gr[k] -> val;
		if(!marked[to] && !marked[to])
			dfs(to);
		gr[k] = gr[k] -> next;
	}

	push(answ, k);
}

void topsort(){
	for(int i = 1;i <= n;i++)
		if(!marked[i])
			dfs(i);

	while(answ != NULL){
		g << answ -> val << " ";
		answ = answ -> next;
	}
}

int main(){

	f >> n >> m;
	while(m--){
		f >> x >> y;
		add(y);
	}

	topsort();
}