Cod sursa(job #1705428)

Utilizator elena.marinicaMarinica Elena-Georgiana elena.marinica Data 20 mai 2016 16:25:33
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <vector>
#include <string.h>
#include <stdio.h>
#include <algorithm>

int t = 0;

void DFS(int node, std::vector<int>g[], int visited[], int tm[]) {
	
	visited[node] = 1;
	tm[node] = t;
	t++;
	
	for (unsigned int i = 0; i < g[node].size(); i++) {
		if (!visited[g[node][i]]) {
			DFS(g[node][i], g, visited, tm);
		}
	}
}

int main() {

	int n, m, x, y;
	
	FILE* fin = fopen("sortaret.in", "r");
	FILE* fout = fopen("sortaret.out", "w");
	
	fscanf(fin, "%d %d", &n, &m);
	
	std::vector<int> graf[n + 1];
	int visited[n + 1];
	int tm[n + 1];
	
	memset(visited, 0, sizeof(int) * (n + 1));
	memset(tm, 0, sizeof(int) * (n + 1));
	
	for (int i = 1; i <= m; i++) {
		fscanf(fin, "%d %d", &x, &y);
		graf[x].push_back(y);
	}
	
	fclose(fin);
	
	DFS(1, graf, visited, tm);
	
	std::vector<std::pair<int, int> > topo;
	
	for (int i = 1; i <= n; i++) {
		topo.push_back(std::make_pair(tm[i], i));
	}
	
	std::sort(topo.begin(), topo.end());
	for (int i = 0; i < n; i++) {
		fprintf(fout, "%d ", topo[i].second);
		
	}
	
	fclose(fout);
}