Cod sursa(job #3353024)

Utilizator Dopamin3_AddictTheo Al Dopamin3_Addict Data 3 mai 2026 18:27:36
Problema Parcurgere DFS - componente conexe Scor 55
Compilator java Status done
Runda Arhiva educationala Marime 1.49 kb
import java.util.*;
import java.io.*; // Necesar pentru File si PrintWriter

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

    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(new File("dfs.in"));
        if (!sc.hasNextInt()) return;

        n = sc.nextInt();
        m = sc.nextInt();


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

        for (int i = 1; i <= m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph[a].add(b);
            graph[b].add(a);
        }

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


        PrintWriter pw = new PrintWriter(new File("dfs.out"));
        pw.println(componente);
        pw.close();
        sc.close();
    }

    private static void dfsIterativ(int startNode) {

        ArrayDeque<Integer> stack = new ArrayDeque<>();
        stack.push(startNode);
        vizitat[startNode] = 1;

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

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