Cod sursa(job #3266288)

Utilizator lucky1992Ion Ion lucky1992 Data 7 ianuarie 2025 11:16:26
Problema Sortare topologica Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 1.84 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 void topologicalSort(DirectGraph g, int u, Deque<Integer> stack, boolean[] visited) {
    visited[u] = true;

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

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

    stack.push(u);
  }



  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];
      for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
          topologicalSort(g, i, stack, visited);
        }
      }

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