Cod sursa(job #2675575)

Utilizator kitkat007Graphy kitkat007 Data 22 noiembrie 2020 00:03:58
Problema Parcurgere DFS - componente conexe Scor 35
Compilator java Status done
Runda Arhiva educationala Marime 2.08 kb
import java.io.*;
import java.util.*;

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 IOException {
        BufferedReader br = new BufferedReader(new FileReader(INPUT_FILE_PATH));
        PrintWriter out = new PrintWriter(OUTPUT_FILE_PATH);
        String[] tokens = br.readLine().split("\\s");
        int n = Integer.parseInt(tokens[0]);
        int m = Integer.parseInt(tokens[1]);
        UndirectedGraph mGraph = new UndirectedGraph(n);
        while (m-- > 0) {
            tokens = br.readLine().split("\\s");
            int source = Integer.parseInt(tokens[0]);
            int dest = Integer.parseInt(tokens[1]);
            mGraph.addEdge(source, dest);
        }
        int c = mGraph.countConnectedComponents();
        out.print(c);
        out.flush();
        br.close();
        out.close();
    }

    static class UndirectedGraph {
        private List<List<Integer>> adjList = new ArrayList<>();
        private int cntNodes;

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

        public void addEdge(int x, int y) {
            this.adjList.get(x).add(y);
            this.adjList.get(y).add(x);
        }

        public int countConnectedComponents() {
            boolean[] visited = new boolean[cntNodes + 1];
            int cnt = 0;
            for (int i = 1; i <= cntNodes; ++i) {
                if (!visited[i]) {
                    ++cnt;
                    dfs(i, visited);
                }
            }
            return cnt;
        }

        private void dfs(int node, boolean[] visited) {
            visited[node] = true;
            for (int relatedNode : this.adjList.get(node)) {
                if (!visited[relatedNode]) {
                    dfs(relatedNode, visited);
                }
            }
        }
    }
}