Cod sursa(job #3266291)

Utilizator lucky1992Ion Ion lucky1992 Data 7 ianuarie 2025 11:31:56
Problema Sortare topologica Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 2.06 kb
import java.io.*;
import java.util.*;

public class Main {

  public static class DirectGraph {
    private List<Integer>[] adjList;

    public DirectGraph(int n) {
      adjList = (List<Integer>[]) new List[n+1];
    }

    public void addEdge(int u, int v) {
      if (adjList[u] == null) {
        adjList[u] = new LinkedList<>();
      }
      adjList[u].add(v);
    }

    public List<Integer> neighbors(int u) {
      if (adjList[u] == null) {
        return Collections.emptyList();
      } else {
        return adjList[u];
      }
    }
  }

  public static int head = 0;


  public static void topologicalSort(DirectGraph g, int u, boolean[] visited, int[] stack) {
    visited[u] = true;

    List<Integer> neighbors = g.neighbors(u);

    if (neighbors != null) {
      for (int v : neighbors) {
        if (!visited[v]) {
          topologicalSort(g, v, visited, stack);
        }
      }
    }

//    stack.push(u);
    stack[head] = u;
    head++;
  }



  public static void main(String[] args) throws IOException {
    try (BufferedReader reader = new BufferedReader(new FileReader("sortaret.in"));
         PrintStream ps = new PrintStream(new FileOutputStream("sortaret.out"), true)) {

      StringTokenizer st = new StringTokenizer(reader.readLine());

      int N = Integer.parseInt(st.nextToken());
      int M = Integer.parseInt(st.nextToken());

      DirectGraph g = new DirectGraph(N);

      for (int i = 0; i < M; i++) {
        st = new StringTokenizer(reader.readLine());
        g.addEdge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
      }


//      Deque<Integer> stack = new LinkedList<>();
      boolean[] visited = new boolean[N+1];
      int[] deque = new int[N+1];
      for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
          topologicalSort(g, i, visited, deque);
        }
      }

      while (head > 0) {
        head--;
        ps.print(deque[head]);
        ps.print(" ");
      }
      ps.println();

//      for (int v : stack) {
//        ps.print(v);
//        ps.print(" ");
//      }
//      ps.println();
    }
  }
}