Cod sursa(job #2125939)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 8 februarie 2018 21:34:28
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.12 kb
import java.io.*;
import java.lang.*;
import java.util.*;

public class main {
    static Scanner fi;
    static PrintWriter fo;

    static Vector<Integer> graph[];
    static boolean f[];

    static int n, m;

    static void dfs(int u) {
        f[u] = true;
        for (int v: graph[u])
            if (!f[v])
                dfs(v);
    }

    public static void main(String[] args) throws IOException {
        int a, b, answer;

        fi = new Scanner(new FileInputStream("dfs.in"));
        fo = new PrintWriter("dfs.out");

        n = fi.nextInt();
        m = fi.nextInt();

        f = new boolean[n];
        graph = new Vector[n];
        for (int i = 0; i < n; ++i)
            graph[i] = new Vector<>();

        for (int i = 0; i < m; ++i) {
            a = fi.nextInt(); a-= 1;
            b = fi.nextInt(); b-= 1;

            graph[a].add(b);
            graph[b].add(a);
        }

        answer = 0;
        for (int i = 0; i < n; ++i) {
            if (!f[i]) {
                answer += 1;
                dfs(i);
            }
        }

        fo.print(answer);

        fi.close();
        fo.close();
    }
}