Cod sursa(job #1866411)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 3 februarie 2017 00:08:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

typedef struct nod{
	int val;
	nod* next;
	
}*graf;

graf lda[100010];
int N,M,C[100000],dr;
bool viz[100010];
void add(graf &a,int x){
	graf b=new nod;
	b->val=x;
	b->next=a;
	a=b;
	
}

void dfs(int x){
	viz[x]=1;
	//cout <<x<<" ";
	
	for(graf r=lda[x];r!=NULL;r=r->next){
		if (!viz[r->val]) dfs(r->val);
		
	}
	C[++dr]=x;
	//rs.push_(x);
	
}

int main(){
	fin >>N>>M;
	for (int i=1;i<=M;i++){
		int x,y;
		fin >>x>>y;
		add(lda[x],y);
	}
	for (int i=1;i<=N;i++) if (!viz[i]) dfs(i);
	for (int i=N;i>=1;i--) fout <<C[i]<<" ";
	
	return 0;
}