Cod sursa(job #1028358)

Utilizator eugen_ptrEugen Patru eugen_ptr Data 13 noiembrie 2013 21:50:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <cstdio>
using namespace std;

struct nod
{
    int inf;
    nod *urm;
}*L[100005];

int n,m,viz[100005];

void add_nod(nod *&prim, int x)
{
    nod *nou= new nod;
    nou->inf=x;
    nou->urm=prim;
    prim=nou;
}

void citire()
{
    scanf("%d%d",&n,&m);
    for (int i=1; i<=m; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add_nod(L[x],y);
        add_nod(L[y],x);
    }
}

void dfs(int vf)
{
    viz[vf]=1;
    for(nod *p=L[vf]; p; p=p->urm)
        if (!viz[p->inf])
            dfs(p->inf);
}

int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    citire();
    int cnt=0;
    for (int i=1; i<=n; i++)
        if (!viz[i])
        {
            cnt++;
            dfs(i);
        }
    printf("%d",cnt);
    return 0;
}