Cod sursa(job #2237422)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 1 septembrie 2018 20:16:09
Problema Sortare topologica Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.1 kb
import static java.util.Objects.requireNonNull;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.List;

public final class Main {
  public static final String IN_FILE = "sortaret.in";
  public static final String OUT_FILE = "sortaret.out";

  public static final class FastScanner implements AutoCloseable {
    private final BufferedReader reader;
    private StringTokenizer tokenizer;

    public FastScanner(final String fileName) throws IOException {
      reader = new BufferedReader(
          new InputStreamReader(new FileInputStream(fileName)));
    }

    private String next() throws IOException {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        final String line = requireNonNull(reader.readLine());
        tokenizer = new StringTokenizer(line);
      }
      return tokenizer.nextToken();
    }

    public int nextInt() throws IOException {
      return Integer.parseInt(next());
    }

    @Override
    public void close() throws IOException {
      reader.close();
    }
  }

  public static void dfs(
      final int[][] graph,
      final int u,
      final boolean[] visited,
      final List<Integer> order) {
    visited[u] = true;
    for (final int v : graph[u]) {
      if (!visited[v]) {
        dfs(graph, v, visited, order);
      }
    }
    order.add(u);
  }

  public static int[] getTopologicalOrder(final int[][] graph) {
    final List<Integer> order = new ArrayList<>();
    final boolean[] visited = new boolean[graph.length];
    for (int u = 0; u < graph.length; u++) {
      if (!visited[u]) {
        dfs(graph, u, visited, order);
      }
    }
    Collections.reverse(order);
    return order.stream().mapToInt(Integer::intValue).toArray();
  }

  public static int[][] readGraph(final FastScanner scanner)
      throws IOException {
    final int size = scanner.nextInt();
    final int edgeCount = scanner.nextInt();
    final int[][] edges = new int[edgeCount][];
    final int[] degrees = new int[size];
    for (int e = 0; e < edgeCount; e++) {
      final int u = scanner.nextInt() - 1;
      final int v = scanner.nextInt() - 1;
      edges[e] = new int[] {u, v};
      degrees[u]++;
    }
    final int[][] graph = new int[size][];
    for (int u = 0; u < size; u++) {
      graph[u] = new int[degrees[u]];
    }
    for (int e = 0; e < edgeCount; e++) {
      final int u = edges[e][0];
      final int v = edges[e][1];
      graph[u][degrees[u] - 1] = v;
      degrees[u]--;
    }
    return graph;
  }

  public static void main(final String[] args) throws IOException {
    try (final FastScanner scanner = new FastScanner(IN_FILE);
        final PrintWriter writer = new PrintWriter(OUT_FILE)) {
      final int[][] graph = readGraph(scanner);
      final int[] order = getTopologicalOrder(graph);
      for (int i = 0; i < order.length; i++) {
        writer.print(order[i]);
        writer.print(i + 1 < order.length ? ' ' : '\n');
      }
    }
  }
}