Pagini recente » Cod sursa (job #2454872) | Cod sursa (job #2964346) | Cod sursa (job #1811440) | Cod sursa (job #2976927) | Cod sursa (job #1728603)
#include <iostream>
#include <fstream>
#include <vector>
#include <iterator>
#define NMAX 50005
using namespace std;
void add(vector<int> *v,int i,int j);
void read(int &n,int &m,vector<int> *v);
void DFS(vector<int> &TSI,vector<int> *v,int *freq,int el);
void TopoSort(int n,vector<int> &TSI,vector<int> *v,int *freq);
int main()
{
ofstream g("sortaret.out");
vector<int> v[NMAX];
vector<int> TSI;
int n,m,freq[NMAX] = {0};
read(n,m,v);
TopoSort(n,TSI,v,freq);
for(int i=TSI.size()-1;i>=0;i--)
g << TSI[i] << " ";
g.close();
return 0;
}
void add(vector<int> *v,int i,int j){
v[i].push_back(j);
}
void read(int &n,int &m,vector<int> *v){
ifstream f("sortaret.in");
int a,b;
f >> n >> m;
for(int i=0;i<m;i++){
f >> a >> b;
add(v,a,b);
}
f.close();
}
void DFS(vector<int> &TSI,vector<int> *v,int *freq,int el){
freq[el]=1;
for(vector<int>::iterator it=v[el].begin();it!=v[el].end();it++){
if(freq[*it]==0)
DFS(TSI,v,freq,*it);
}
TSI.push_back(el);
}
void TopoSort(int n,vector<int> &TSI,vector<int> *v,int *freq){
for(int i=1;i<=n;i++)
if(freq[i]==0)
DFS(TSI,v,freq,i);
}