Cod sursa(job #3272371)

Utilizator AbrianPetruta Adrian Abrian Data 29 ianuarie 2025 11:18:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <bits/stdc++.h>

using namespace std;

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

struct nod
{
    int indice;
    nod *urm;
}*v[100005];

int viz[100005],n,m,x,y,k;

void add(int x,nod *&dest)
{
    nod *p;
    p=new nod;
    p->indice=x;
    p->urm=dest;
    dest=p;
}

void DF(int x)
{
    viz[x]=1;
    for(nod *p=v[x];p;p=p->urm)
        if(viz[p->indice]==0)
            DF(p->indice);

}

int main()
{
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>x>>y;
        add(x,v[y]);
        add(y,v[x]);
    }
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
        {
            k++;
            DF(i);
        }
    out<<k<<'\n';
    return 0;
}