Cod sursa(job #3298715)

Utilizator iulia.petrisorIulia Alexia Petrisor iulia.petrisor Data 31 mai 2025 23:41:47
Problema Parcurgere DFS - componente conexe Scor 50
Compilator java Status done
Runda Arhiva educationala Marime 1.35 kb
import java.io.File;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    static boolean[] visited;
    static ArrayList<Integer>[] adj;

    static void dfs(int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        visited[start] = true;

        while (!stack.isEmpty()) {
            int node = stack.pop();
            for (int neigh : adj[node]) {
                if (!visited[neigh]) {
                    visited[neigh] = true;
                    stack.push(neigh);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new File("dfs.in"));
        PrintWriter out = new PrintWriter("dfs.out");

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

        adj = new ArrayList[n + 1];
        visited = new boolean[n + 1];

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

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

        int cc = 0;
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                cc++;
                dfs(i); // DFS, dar iterativ!
            }
        }

        out.println(cc);
        out.close();
    }
}