Cod sursa(job #3353025)

Utilizator Dopamin3_AddictTheo Al Dopamin3_Addict Data 3 mai 2026 18:29:48
Problema Parcurgere DFS - componente conexe Scor 90
Compilator java Status done
Runda Arhiva educationala Marime 2.08 kb
import java.util.*;
import java.io.*;

public class Main {
    static int n, m;
    static ArrayList<Integer>[] graph;
    static int[] vizitat;

    // Clasa pentru citire rapida
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader(String fileName) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(fileName));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }

    public static void main(String[] args) throws IOException {
        FastReader fr = new FastReader("dfs.in");
        n = fr.nextInt();
        m = fr.nextInt();


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

        for (int i = 0; i < m; i++) {
            int u = fr.nextInt();
            int v = fr.nextInt();
            graph[u].add(v);
            graph[v].add(u);
        }

        vizitat = new int[n + 1];
        int componente = 0;

        for (int i = 1; i <= n; i++) {
            if (vizitat[i] == 0) {
                componente++;
                dfsIterativ(i);
            }
        }

        PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("dfs.out")));
        pw.println(componente);
        pw.close();
    }

    private static void dfsIterativ(int startNode) {

        ArrayDeque<Integer> stack = new ArrayDeque<>();

        stack.push(startNode);
        vizitat[startNode] = 1;

        while (!stack.isEmpty()) {
            int node = stack.pop();

            for (int neigh : graph[node]) {
                if (vizitat[neigh] == 0) {
                    vizitat[neigh] = 1;
                    stack.push(neigh);
                }
            }
        }
    }
}