Mai intai trebuie sa te autentifici.
Cod sursa(job #2691568)
Utilizator | Data | 29 decembrie 2020 12:04:04 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 1.05 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
unsigned int N,M,x,y;
vector< vector<unsigned int> > adj;
stack<unsigned int> sortare_topo;
vector<char> visited;
void Read(){
fin >> N >> M; adj = vector< vector<unsigned int> >(N+1);//aloc N linii
visited = vector<char>(N+1);
while(fin >> x >> y){
adj[x].push_back(y);
}
}
void DFS(unsigned int nod){
visited[nod] = '1';
for(int n = 0; n < adj[nod].size(); n++)
if(visited[n]=='0')
DFS(n);
//inserez in lista
sortare_topo.push(nod);
}
void ConstructSort(){
for(int i = 1; i <= N; i++)
visited[i] = '0';
for(int i = 1; i <= N; i++){
if(visited[i] == '0')
DFS(i);
}
}
void Display_Sort(){
while(!sortare_topo.empty()){
fout << sortare_topo.top() << " ";
sortare_topo.pop();
}
}
int main(){
Read();
ConstructSort();
Display_Sort();
/*for(int i = 1; i <= N; i++){
for(int j = 0; j < adj[i].size(); j++){
cout << adj[i][j] << " ";
}
cout << endl;
}*/
return 0;
}