Cod sursa(job #2851407)

Utilizator k2y201342asdfadfsafsd k2y20 Data 18 februarie 2022 16:26:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N=1e5+5;

struct lista
{
    vector <int> v;
    bool parcurs;
    int componenta;
}la[N];

void dfs(int nod)
{
    if(la[nod].parcurs) return;
    la[nod].parcurs=1;

    for(int i=0;i<la[nod].v.size();i++)
    {
        dfs(la[nod].v[i]);
        la[la[nod].v[i]].componenta=la[nod].componenta;
    }
}

int main()
{
    int n,m,nrComponente=0;
    in>>n>>m;

    for(int i=1;i<=m;i++)
    {
        int x,y;
        in>>x>>y;

        la[x].v.push_back(y);
        la[y].v.push_back(x);
    }

    for(int i=1;i<=n;i++)
    {
        if(!la[i].parcurs)
        {
            la[i].componenta=++nrComponente;
            dfs(i);
        }
    }
    out<<nrComponente;
    return 0;
}