Cod sursa(job #2902242)

Utilizator LucaB26Batori Luca LucaB26 Data 15 mai 2022 22:36:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <fstream>
#include <vector>

using namespace std;
int n,m,a,b,k,i;

ifstream cin("dfs.in");
ofstream cout("dfs.out");

struct nod{
    int fost;
    vector<int> v;
};

vector <nod>x;

void df(int p)
{
    x[p].fost=1;
    for(auto &e:x[p].v)
        if(x[e].fost==0)df(e);
}



int main()
{
    cin>>n>>m;
    x.resize(n+1);
    for(i=1;i<=m;++i)
    {
        cin>>a>>b;
        x[a].v.push_back(b);
        x[b].v.push_back(a);
    }
    k=0;
    for(i=1;i<=n;++i)
    {
        if(x[i].fost==0)
        {
            k++;
            df(i);
        }
    }
    cout<<k;
    return 0;
}