Cod sursa(job #3298713)

Utilizator iulia.petrisorIulia Alexia Petrisor iulia.petrisor Data 31 mai 2025 23:40:18
Problema Parcurgere DFS - componente conexe Scor 55
Compilator java Status done
Runda Arhiva educationala Marime 1.14 kb
import java.io.File;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Scanner;

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

    static void dfs(int src) {
        visited[src] = true;
        for (int neigh : adj[src]) {
            if (!visited[neigh]) {
                dfs(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);
            }
        }

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