Cod sursa(job #2606359)

Utilizator lev.tempfliTempfli Levente lev.tempfli Data 27 aprilie 2020 16:18:23
Problema Parcurgere DFS - componente conexe Scor 25
Compilator java Status done
Runda Arhiva educationala Marime 1.62 kb


import java.io.*;
import java.util.*;

public class Main {

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

        FileWriter fileWriter = new FileWriter("dfs.out");
        PrintWriter printWriter = new PrintWriter(fileWriter);

        printWriter.print(graph.num_conn_comp());

        printWriter.close();
        fileWriter.close();
    }
}

class Graph {
    public Graph(final String filename) throws FileNotFoundException {
        File file = new File(filename);
        Scanner scanner = new Scanner(file);
        int n, m;
        n = scanner.nextInt();
        m = scanner.nextInt();
        adj_list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj_list.add(new ArrayList<>());
        }

        int f, g, h;
        for (int i = 0; i < m; i++) {
            f = scanner.nextInt();
            g = scanner.nextInt();
            adj_list.get(f).add(g);
            adj_list.get(g).add(f);
        }

        scanner.close();
    }

    public int num_conn_comp() {
        ArrayList<Boolean> seen = new ArrayList<>(Collections.nCopies(adj_list.size(), Boolean.FALSE));
        int k = 0;
        for (int i = 1; i < adj_list.size(); i++) {
            if (seen.get(i) == Boolean.FALSE) {
                k++;
                dfs(i, seen);
            }
        }
        return k;
    }

    private void dfs(int i, ArrayList<Boolean> seen) {
        if (seen.get(i) == Boolean.TRUE) return;
        seen.set(i, Boolean.TRUE);
        for (int e : adj_list.get(i))
            dfs(e, seen);
    }


    private ArrayList<ArrayList<Integer>> adj_list;
};