Cod sursa(job #3205091)

Utilizator TrifoitaBejenescu-Babusanu Stefan Trifoita Data 18 februarie 2024 19:09:23
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

struct Node{
  int data;
  struct Node *next;
};

int n, m, k =0;
struct Node *List[50001];
int used[50001], v[50001];

void read_graph() {
  fin >> n >> m;;
  int i, j;
  for (int x = 1; x <= m; x++) {
    fin >> i >> j;
    struct Node *c = new Node;
    c -> data = j;
    c -> next = List[i];
    List[i] = c;
  }
}

void dfs(int node) {
  used[node] = 1;
  struct Node *c = List[node];
  while (c) {
    if (!used[c->data]) {
      dfs(c->data);
    }
    c = c -> next;
  }
  v[++k] = node;
}

// void read() {
//   fin >> n >> m;
//   for (int i = 1; i <= m; i++) {
//     int i, j; fin >> i >> j;
//     matrix[i][j] = 1;
//   }
// }
//
// void dfs() {
//
// }

int main() {
  read_graph();
  for (int node = 1; node <= n; node++)
    if (!used[node])
      dfs(node);
  for (int i = k; i >= 1; i--)
    fout << v[i] << " ";
  return 0;
}