Cod sursa(job #3122842)

Utilizator andreidrago14@yahoo.comDragomir Andrei [email protected] Data 20 aprilie 2023 19:35:19
Problema Parcurgere DFS - componente conexe Scor 55
Compilator java Status done
Runda Arhiva educationala Marime 3.07 kb
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;



public class Main {
    static class Task {
        public static final String INPUT_FILE = "dfs.in";
        public static final String OUTPUT_FILE = "dfs.out";

        // numarul maxim de noduri
        public static final int NMAX = (int)1e5 + 5; // 10^5 + 5 = 100.005

        // n = numar de noduri, m = numar de muchii/arce
        int n, m;

        // adj[node] = lista de adiacenta a nodului node
        // exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
        @SuppressWarnings("unchecked")
        ArrayList<Integer> adj[] = new ArrayList[NMAX];

        public void solve() {
            readInput();
            writeOutput(getResult());
        }

        private void readInput() {
            try {
                Scanner sc = new Scanner(new BufferedReader(new FileReader(
                        INPUT_FILE)));
                n = sc.nextInt();
                m = sc.nextInt();

                for (int node = 1; node <= n; node++) {
                    adj[node] = new ArrayList<>();
                }

                for (int i = 1, x, y; i <= m; i++) {
                    // arc (x, y)
                    x = sc.nextInt();
                    y = sc.nextInt();
                    adj[x].add(y);
                    adj[y].add(x);
                }

                sc.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        private void writeOutput(Integer result) {
            try {
                PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter(
                        OUTPUT_FILE)));
                pw.printf("%d", result);
                pw.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        private void bfs(int node, int[] visited) {
            Queue<Integer> q = new LinkedList<>();
            q.add(node);
            visited[node] = 1;

            while (!q.isEmpty()) {
                int curr = q.poll();
                for (Integer neigh : adj[curr]) {
                    if (visited[neigh] == 0) {
                        visited[neigh] = 1;
                        q.add(neigh);
                    }
                }
            }
        }

        private Integer getResult() {
            int[] visited = new int[n + 1];
            for (int i = 0; i <= n; i++) {
                visited[i] = 0;
            }

            Integer result = 0;
            for (int node = 1; node <= n; node++) {
                if (visited[node] == 0) {
                    bfs(node, visited);
                    result = result + 1;
                }
            }

            return result;
        }
    }

    public static void main(String[] args) {
        new Task().solve();
    }
}