Cod sursa(job #2305995)

Utilizator flatmapLambda flatmap Data 21 decembrie 2018 14:18:25
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.01 kb
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    private static final String INPUT_FILE_PATH = "dfs.in";
    private static final String OUTPUT_FILE_PATH = "dfs.out";

    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(new FileReader(INPUT_FILE_PATH));
        int n = sc.nextInt();
        UndirectedGraph graph = new UndirectedGraph(n);
        int m = sc.nextInt();
        while (m-- > 0) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            --from;
            --to;
            graph.addEdge(from, to);
        }
        PrintWriter pw = new PrintWriter(OUTPUT_FILE_PATH);
        pw.println(graph.getConnectedComponents());
        pw.flush();
    }

    static class UndirectedGraph {
        private int n;
        private List<List<Integer>> adjMatrix;
        boolean[] visited;

        UndirectedGraph(int n) {
            this.n = n;
            adjMatrix = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                adjMatrix.add(new ArrayList<>());
            }
        }

        void addEdge(int from, int to) {
            adjMatrix.get(from).add(to);
            adjMatrix.get(to).add(from);
        }

        int getConnectedComponents() {
            visited = new boolean[n];
            Arrays.fill(visited, false);
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (!visited[i]) {
                    ++cnt;
                    dfs(i);
                }
            }
            return cnt;
        }

        private void dfs(int node) {
            visited[node] = true;
            adjMatrix.get(node).forEach(child -> {
                if (!visited[child]) {
                    dfs(child);
                }
            });
        }
    }
}