Cod sursa(job #3122961)

Utilizator DrugeaDianaDrugea Diana DrugeaDiana Data 21 aprilie 2023 13:22:37
Problema Parcurgere DFS - componente conexe Scor 5
Compilator java Status done
Runda Arhiva educationala Marime 2.6 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.ArrayList;
import java.util.Scanner;

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);
                }

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

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

        private boolean[] viz;

        private void DFS(int node) {
            viz[node] = true;
            for (int neigh : adj[node]) {
                if (!viz[neigh]) {
                    DFS(neigh);
                }
            }
        }

        private int getResult() {
            viz = new boolean[n + 1];

            int nrComp = 0;
            for (int i = 1; i <= n; i++) {
                if (!viz[i]) {
                    nrComp++;
                    DFS(i);
                }
            }

            return nrComp;
        }
    }

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