Cod sursa(job #3238031)

Utilizator Her0ninjaDragos Rolland Her0ninja Data 15 iulie 2024 17:32:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

void dfs(int c, vector<vector<int>>& z, vector<bool>& l) {
    l[c]=true;
    for (int s:z[c]) {
        if (!l[s]) {
            dfs(s,z,l);
        }
    }
}

int main()
{
    ifstream f("dfs.in");
    ofstream g("dfs.out");
    int N,M;
    f>>N>>M;
    vector<vector<int>> z(N+1);
    vector<bool> l(N+1,false);

    for (int i=0;i<M;i++) {
        int X,Y;
        f>>X>>Y;
        z[X].push_back(Y);
        z[Y].push_back(X);
    }
    int k=0;

    for (int i=1;i<=N;i++) {
        if (!l[i]) {
            dfs(i,z,l);
            k++;
        }
    }
    g<<k<<endl;
    f.close();
    g.close();
    return 0;
}