Pagini recente » Cod sursa (job #1101404) | Cod sursa (job #1144837) | Cod sursa (job #1989253) | Profil melania.patru | Cod sursa (job #1978916)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
stack<int> sorted;
vector<int> descoperire;
vector<int> finalizare;
vector<bool> visited;
int timp = 1;
void dfs(vector<int> *G, int node);
void sortare_topologica(vector<int> G[], int& N) {
for(int i = 1; i <= N; i++){
if(!visited[i]){
dfs(G, i);
}
}
}
void dfs(vector<int> *G, int node){
descoperire[node] = timp++;
visited[node] = true;
int vecini = G[node].size();
for(int i : G[node]){
if(descoperire[i] != 0 && finalizare[i] == 0){
printf("Ciclu la %d, parinte: %d\n", i, node);
}
if(!visited[i]){
dfs(G, i);
}
}
finalizare[node] = timp++;
sorted.push(node);
}
int main() {
FILE *fp = fopen("sortaret.in", "r");
int N, M;
fscanf(fp, "%d%d", &N, &M);
vector<int> G[N+1];
visited = vector<bool>(N+1, false);
descoperire = vector<int>(N+1, 0);
finalizare = vector<int>(N+1, 0);
int x, y;
for(int i = 0; i < M; i++) {
fscanf(fp, "%d%d", &x, &y);
G[x].push_back(y);
}
fclose(fp);
sortare_topologica(G, N);
FILE *out = fopen("sortaret.out", "w");
while(!sorted.empty()){
fprintf(out, "%d ", sorted.top());
sorted.pop();
}
fclose(out);
return 0;
}