Cod sursa(job #3032862)

Utilizator anutza39Ana-Ioana Cristescu anutza39 Data 22 martie 2023 21:26:39
Problema Parcurgere DFS - componente conexe Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 4.06 kb
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.*;

public class Graf {
    public static void main(String[] args) throws FileNotFoundException {
        File in = new File("dfs.in");
        Scanner sc = new Scanner(in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        Graf graf = new Graf(n);

        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            graf.adaugareMuchie(x,y);
        }
        //in mom acesta avem graful facut

        int nrConexe = 0;
        for (int i = 1; i <= n; i++) {
            if (graf.viz[i]) continue;
            graf.dfs(i);
            nrConexe++;
        }

        File out = new File("dfs.out");
        PrintStream p = new PrintStream(out);

        p.println(nrConexe);
        // Daca nu inchidem fisierul, nu se salveaza!!
        p.close();
    }

    // numarul de varfuri
    public final int N;
    // vector de vizitare
    private final boolean[] viz;

    // listele de adiacenta
    public final List<List<Integer>> adjLists;

    // matricea de adiacenta
    public final boolean[][] adjMatrix;


    public Graf(int n) {
        this.N = n;
        viz = new boolean[n + 1];
        // VARIANTA CU LISTE ADIACENTA

        // n + 1 pt ca vom incepe numerotarea de la 1 in loc de 0 (indexul 0 va fi ignorat)
        adjLists = new ArrayList<>(n + 1);
        adjLists.add(null); // valoarea de la index 0 este null (nu e folosita)

        for (int i = 1; i <= n; i++) {
            adjLists.add(new ArrayList<>());
        }

        // VARIANTA CU MATRICE DE ADIACENTA
        // acelasi motiv ca la lista
        adjMatrix = new boolean[n + 1][n + 1];
    }

    // pentru graf orientat
    public void adaugareArc(int sursa, int destinatie) {
        List<Integer> list = adjLists.get(sursa);
        list.add(destinatie);

        adjMatrix[sursa][destinatie] = true;
    }

    // pentru graf neorientat
    public void adaugareMuchie(int a, int b) {
        adaugareArc(a, b);
        adaugareArc(b, a);
    }

    public boolean existaArc(int sursa, int destinatie) {
        // varianta cu matrice
        //return adjMatrix[sursa][destinatie];

        // varianta cu liste de adiacenta
        List<Integer> list = adjLists.get(sursa);
        return list.contains(destinatie);
    }

    // complexitate O(N + M)
    // functia se apeleaza de n ori
    // interior-ul forului de m ori
    public void dfs(int start) {
        viz[start] = true;

        List<Integer> list = adjLists.get(start);
        for (int urm : list) {
            if (viz[urm]) continue;
            dfs(urm);
        }
        // pentru matrice
//        for (int j = 1; j <= N; j++) {
//            if (adjMatrix[start][j] == false) continue;
//            if (viz[j]) continue;
//            if (dfsHelper(j, destinatie)) return true;
//        }
    }


    // tot O(N + M)
    public boolean bfs(int start, int destinatie) {
        for (int i = 1; i <= N; i++) viz[i] = false;

        // deque functioneaza ca coada si stiva simultan
        Deque<Integer> queue = new ArrayDeque<>();
        // initial, coada contine doar start-ul
        queue.addLast(start);
        // marcam start-ul ca fiind vizitat (adaugat in coada)
        viz[start] = true;


        while (!queue.isEmpty()) {
            // se ia urmatorul nod din coada
            int nod = queue.removeFirst();
            // verificam daca am ajuns la destinatie
            if (nod == destinatie) return true;

            // adaugam toate nodurile urmatoare posibile in coada
            List<Integer> listaNodului = adjLists.get(nod);
            for (int urm : listaNodului) {
                // le sarim pe cele care sunt deja in coada
                if (viz[urm]) continue;
                // adaugam in coada si marcam ca vizitat
                queue.addLast(urm);
                viz[urm] = true;
            }
        }

        return false;
    }
}