Pagini recente » Cod sursa (job #2388722) | Cod sursa (job #258308) | Cod sursa (job #3178723) | Cod sursa (job #280227) | Cod sursa (job #1975347)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>
#define WHITE 0
#define BLACK 1
#define GREY 2
void dfs();
void explore(int node);
std::vector<std::vector<int>> graph;
std::vector<int> colors;
std::vector<int> distance;
int T = 0;
int number = 0;
int main() {
int N,M;
FILE *in = fopen("sortaret.in","r");
FILE *out = fopen("sortaret.out","w");
fscanf(in,"%d",&N);
fscanf(in,"%d",&M);
for(int i = 0; i < N; i++) {
std::vector<int> temp;
graph.push_back(temp);
distance.push_back(INT32_MAX);
}
for(int i = 0; i < M; i++) {
int start,end;
fscanf(in,"%d %d",&start,&end);
if(start != end) {
graph[start - 1].push_back(end - 1);
}
}
dfs();
int help[graph.size()];
for(int i = 0; i < graph.size(); i++) {
help[i] = i;
}
for(int i = 0; i < graph.size(); i++) {
for (int j = 0; j < graph.size(); j++) {
if(distance[i] > distance[j]) {
int aux1 = distance[i];
distance[i] = distance[j];
distance[j] = aux1;
int aux2 = help[i];
help[i] = help[j];
help[j] = aux2;
}
}
}
for(int i = graph.size() - 1; i >= 1; i--) {
fprintf(out,"%d ",help[i] + 1);
}
fprintf(out,"%d",help[0] + 1);
fclose(in);
fclose(out);
return 0;
}
void dfs() {
for(int i = 0; i < graph.size(); i++) {
colors.push_back(WHITE);
}
T = 0;
for(int i = 0; i < graph.size(); i++) {
if( colors[i] == WHITE ) {
explore(i);
number++;
}
}
}
void explore(int node) {
distance[node] = T++;
colors[node] = GREY;
for(int neightbords : graph[node]) {
if (colors[neightbords] == WHITE) {
explore(neightbords);
}
}
colors[node] = BLACK;
T++;
}