Cod sursa(job #3353023)

Utilizator Dopamin3_AddictTheo Al Dopamin3_Addict Data 3 mai 2026 18:23:58
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.03 kb

import java.util.ArrayList;
import java.util.Scanner;

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

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n  = sc.nextInt();
        m = sc.nextInt();
        graph = new ArrayList[n+1];



        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<>();
        }
        int a,b;
        for(int i=1;i<=m;i++){
            a = sc.nextInt();
            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){
                dfs(i);
                componente++;
            }
        }
        System.out.println(componente);
    }
    private static void dfs(int nod){
        vizitat[nod] = 1;
        for(int vecin : graph[nod]){
            if(vizitat[vecin] == 0){
                dfs(vecin);
            }
        }

    }
}