Cod sursa(job #2125958)

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

public class Main {
    static Vector<Integer>[] graph;
    static boolean[] f;

    private 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 {
        Scanner fi = new Scanner(new FileInputStream("dfs.in"));
        PrintWriter fo = new PrintWriter("dfs.out");
        int n, m, a, b;

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

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

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

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

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

        fo.printf("%d\n", answer);

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