Pagini recente » Cod sursa (job #1482398) | Cod sursa (job #606900) | Cod sursa (job #3208166) | Cod sursa (job #2840733) | Cod sursa (job #1527747)
/**
Given a directed graph with N vertices and M edges, print the topological sort of the graph's vertices (if there is an edge from i to j, then i comes before j in the topological sort).
1 <= N <= 50,000
1 <= M <= 100,000
**/
#include <cstdio>
#include <vector>
#include <stack>
#define NMAX 50005
using namespace std;
int N, M;
bool seen[NMAX];
vector <int> graph[NMAX];
stack <int> solution;
void read() {
int vertex1, vertex2;
scanf("%d %d", &N, &M);
for (int i = 1; i <= M; ++i) {
scanf("%d %d", &vertex1, &vertex2);
graph[vertex1].push_back(vertex2);
}
}
void DFS(int vertex) {
vector <int> :: iterator it;
seen[vertex] = true;
for (it = graph[vertex].begin(); it != graph[vertex].end(); ++it) {
if (seen[*it] == false) {
DFS(*it);
}
}
solution.push(vertex);
}
void print() {
while (solution.empty() == false) {
printf("%d ", solution.top());
solution.pop();
}
}
int main() {
read();
for (int vertex = 1; vertex <= N; ++vertex) {
if (seen[vertex] == false)
DFS(vertex);
}
print();
}