Cod sursa(job #2871719)

Utilizator MichaelXcXCiuciulete Mihai MichaelXcX Data 15 martie 2022 16:45:33
Problema Parcurgere DFS - componente conexe Scor 65
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <vector>

#define NMAX 100005

using namespace std;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

void DFS(vector<int> Edges[], int start, bool visited[]) {
    visited[start] = 1;
    for(unsigned int i = 0; i < Edges[start].size(); ++i) {
        int next = Edges[start][i];
        if(!visited[next])
            DFS(Edges, next, visited);
    }
}

int main() {
    int n, m, CTC = 0;
    bool visited[NMAX];
    vector<int> Edges[NMAX];

    fin >> n >> m;

    for(int i = 0; i < m; ++i) {
        int x, y;
        fin >> x >> y;
        Edges[x].push_back(y);
        Edges[y].push_back(x);
    }

    for(int i = 0; i < n; ++i) {
        if(!visited[i]) {
            CTC++;
            DFS(Edges, i, visited);
        }
    }

    fout << CTC;
    
    return 0;
}