Cod sursa(job #1980006)

Utilizator ploxizAlexandru Moscu ploxiz Data 11 mai 2017 21:37:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator java Status done
Runda Arhiva educationala Marime 3.12 kb
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        MyScanner in = new MyScanner("dfs.in");
        PrintWriter out = new PrintWriter("dfs.out");

        int n = in.nextInt();
        int m = in.nextInt();

        List<Node<Integer>> graph = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            graph.add(new Node<>(i));
        }

        for (int i = 0; i < m; i++) {
            int u = in.nextInt() - 1;
            int v = in.nextInt() - 1;

            if (u == v) continue;

            Node<Integer> nodeU = graph.get(u);
            Node<Integer> nodeV = graph.get(v);

            nodeU.neighbours.add(nodeV);
            nodeV.neighbours.add(nodeU);
        }

        int count = 0;

        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                count++;
                DFS(graph.get(i), visited);
            }
        }

        out.println(count);

        out.close();
        in.close();
    }

    private static int[] BFS(Node<Integer> s, int n) {
        Queue<Node<Integer>> queue = new LinkedList<>();

        int[] costs = new int[n];
        Arrays.fill(costs, -1);
        costs[s.value] = 0;

        queue.add(s);
        s.visited = true;

        while (!queue.isEmpty()) {
            Node<Integer> u = queue.poll();

            for (Node<Integer> v : u.neighbours) {
                if (!v.visited) {
                    costs[v.value] = costs[u.value] + 1;
                    v.visited = true;
                    queue.add(v);
                }
            }
        }

        return costs;
    }

    private static void DFS(Node<Integer> u, boolean[] visited) {
        for (Node<Integer> v : u.neighbours) {
            if (!visited[v.value]) {
                visited[v.value] = true;
                DFS(v, visited);
            }
        }
    }

    private static class Node<T> {

        private T value;
        private boolean visited;
        private List<Node<Integer>> neighbours;

        public Node(T value) {
            this.value = value;
            this.visited = false;
            this.neighbours = new ArrayList<>();
        }

    }

    private static class MyScanner {

        private BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;

        MyScanner(String filename) throws FileNotFoundException {
            bufferedReader = new BufferedReader(new FileReader(filename));
        }

        private String next() throws IOException {
            while (stringTokenizer == null || !stringTokenizer.hasMoreElements()) {
                stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            }

            return stringTokenizer.nextToken();
        }

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

        void close() throws IOException {
            bufferedReader.close();
        }
    }
}