Cod sursa(job #2263584)

Utilizator FilpTeodorFilp Teodor FilpTeodor Data 18 octombrie 2018 20:29:59
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

int verticesNumber, edgeNumber;
vector<int> *adj, v;
bool *visited;

void sortareTipologica(int s);
void addEdge(int v, int w);
int main(){

	ifstream read("sortaret.in");
	ofstream write("sortaret.out");

	read>>verticesNumber>>edgeNumber;
	adj = new vector<int>[verticesNumber];
	visited = new bool[verticesNumber];

	for(int i=0; i<verticesNumber; i++)
		visited[i] = false;

	for(int i=0; i<edgeNumber; i++){
		int x, y;
		read>>x>>y;
		x--;
		y--;
		addEdge(x, y);
	}
	cout<<endl;
	for(int i=0; i<verticesNumber; i++){
		sort(adj[i].begin(), adj[i].end());
	}
	sortareTipologica(0);

	for(int i=0; i<verticesNumber; i++)
		write<<v[i]<<" " ;

	return 0;
}

void sortareTipologica(int s){

	visited[s] = true;
	v.push_back(s+1);
	vector<int>::iterator it = adj[s].begin();

	for(; it!=adj[s].end(); ++it){
		if(!visited[*it]){
			sortareTipologica(*it);
		}
	}

	

}

void addEdge(int v, int w){
	adj[v].push_back(w);
}