Cod sursa(job #2022464)

Utilizator gabib97Gabriel Boroghina gabib97 Data 16 septembrie 2017 16:43:36
Problema Parcurgere DFS - componente conexe Scor 85
Compilator java Status done
Runda Arhiva educationala Marime 1.71 kb
import java.util.*;
import java.io.*;

public class Main {
    static boolean[] o;
    static Vector<Integer>[] G;

    private static void DFS(int s) {
        o[s] = true;

        for (int x : G[s])
            if (!o[x]) DFS(x);
    }

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

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

        G = new Vector[n + 1];
        for (int i = 1; i <= n; i++) G[i] = new Vector<>();
        o = new boolean[n + 1];

        G[1].add(3);
        int x, y;
        while (m-- != 0) {
            x = cin.nextInt();
            y = cin.nextInt();
            G[x].add(y);
            G[y].add(x);
        }

        int nr = 0;
        while (n-- != 0)
            if (!o[n + 1]) {
                nr++;
                DFS(n + 1);
            }

        cout.printf("%d", nr);
        cout.close();
    }

    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();
        }
    }
}