Cod sursa(job #3122956)

Utilizator dorinm17Manea Dorin dorinm17 Data 21 aprilie 2023 13:12:50
Problema Parcurgere DFS - componente conexe Scor 55
Compilator java Status done
Runda Arhiva educationala Marime 2.03 kb
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(new File("dfs.in"));
        FileWriter fw = new FileWriter("dfs.out");

        int n;
        long m;
        ArrayList<Integer>[] adj = new ArrayList[(int) 1e5 + 1];

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

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

        for (int i = 1; i <= m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            adj[x].add(y);
            adj[y].add(x);
        }

        int nrCC = 0;
        // Rezolva folosind Stack, iterativ
//        Stack<Integer> stack = new Stack<>();
//        boolean[] visited = new boolean[n + 1];
//
//        for (int i = 1; i <= n; i++) {
//            if (!visited[i]) {
//                nrCC++;
//                stack.push(i);
//                visited[i] = true;
//                while (!stack.isEmpty()) {
//                    int node = stack.pop();
//                    for (int neigh : adj[node]) {
//                        if (!visited[neigh]) {
//                            stack.push(neigh);
//                            visited[neigh] = true;
//                        }
//                    }
//                }
//            }
//        }

        // Rezolva folosind recursivitate
        boolean[] visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            if (!visited[i]) {
                nrCC++;
                dfs(i, adj, visited);
            }
        }

        fw.write(String.valueOf(nrCC));

        sc.close();
        fw.close();
    }

    private static void dfs(int i, ArrayList<Integer>[] adj, boolean[] visited) {
        visited[i] = true;
        for (int neigh : adj[i]) {
            if (!visited[neigh]) {
                dfs(neigh, adj, visited);
            }
        }
    }
}