Cod sursa(job #2238840)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 7 septembrie 2018 21:29:24
Problema Parcurgere DFS - componente conexe Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 3.68 kb
import static java.lang.Character.isDigit;
import static java.util.Arrays.fill;
import static java.util.Objects.requireNonNull;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

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

  public static final class FastScanner implements AutoCloseable {
    private static final int BUFFER_SIZE = 1 << 16;

    private final DataInputStream stream;
    private final byte[] buffer = new byte[BUFFER_SIZE];
    private int bufferPointer = 0;
    private int bytesRead = 0;

    public FastScanner(final String fileName) throws IOException {
      stream = new DataInputStream(new FileInputStream(fileName));
    }

    public int nextInt() throws IOException {
      byte c;
      do {
        c = read();
      } while (c != '-' && !isDigit(c));
      final boolean isNegative = c == '-';
      if (isNegative) {
        c = read();
      }
      int value = 0;
      do {
        value = value * 10 + (c - '0');
        c = read();
      } while (isDigit(c));
      return isNegative ? -value : value;
    }

    private byte read() throws IOException {
      final byte c = tryRead();
      if (c == -1) {
        throw new IOException("Reached end of stream!");
      }
      return c;
    }

    private byte tryRead() throws IOException {
      if (bufferPointer == bytesRead) {
        bufferPointer = 0;
        bytesRead = stream.read(buffer, 0, BUFFER_SIZE);
        if (bytesRead == -1) {
          bytesRead = 0;
          return -1;
        }
      }
      return buffer[bufferPointer++];
    }

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

  public static final class Graph {
    private final int[][] graph;
    private final boolean[] visited;

    public Graph(
        final int size, final int edges, final int[] us, final int[] vs) {
      final int[] degrees = new int[size];
      for (int e = 0; e < edges; e++) {
        degrees[us[e]]++;
        degrees[vs[e]]++;
      }
      graph = new int[size][];
      for (int u = 0; u < size; u++) {
        graph[u] = new int[degrees[u]];
      }
      for (int e = 0; e < edges; e++) {
        final int u = us[e];
        final int v = vs[e];
        graph[u][degrees[u] - 1] = v;
        graph[v][degrees[v] - 1] = u;
        degrees[u]--;
        degrees[v]--;
      }
      visited = new boolean[size];
    }

    public int countComponents() {
      fill(visited, false);
      int components = 0;
      for (int u = 0; u < graph.length; u++) {
        if (!visited[u]) {
          components++;
          dfs(u);
        }
      }
      return components;
    }

    private void dfs(final int u) {
      visited[u] = true;
      for (final int v : graph[u]) {
        if (!visited[v]) {
          dfs(v);
        }
      }
    }
  }

  public static Graph readGraph(final FastScanner scanner) throws IOException {
    final int size = scanner.nextInt();
    final int edges = scanner.nextInt();
    final int[] us = new int[edges];
    final int[] vs = new int[edges];
    for (int e = 0; e < edges; e++) {
      us[e] = scanner.nextInt() - 1;
      vs[e] = scanner.nextInt() - 1;
    }
    return new Graph(size, edges, us, vs);
  }

  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 Graph graph = readGraph(scanner);
      final int components = graph.countComponents();
      writer.println(components);
    }
  }
}