Cod sursa(job #1025031)

Utilizator cristitamasTamas Cristian cristitamas Data 9 noiembrie 2013 13:57:49
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>
using namespace std;

struct Nod
{
    int Inf;
    Nod *Urm;
}*Sir[100005];

int Viz[100005];
int N,M,Nr;

void Add(Nod *&Prim,int x)
{
    Nod *nou;
    nou=new Nod;
    nou->Inf=x;
    nou->Urm=Prim;
    Prim=nou;
}

void Citire()
{
    int x,y;
    scanf("%d %d",&N,&M);
    for(int i=0;i<M;++i)
    {
        scanf("%d %d",&x,&y);
        Add(Sir[x],y);
        Add(Sir[y],x);

    }
}

void DFS(int x)
{
    Viz[x]=1;
    for(Nod *P=Sir[x];P!=NULL;P=P->Urm)
        if(!Viz[P->Inf])
            DFS(P->Inf);
}



int main()
{
    freopen("dfs.in","r",stdin);
    freopen("dfs.out","w",stdout);
    Citire();
    for(int i=1;i<=N;++i)
        if(!Viz[i])
        {
            DFS(i);
            Nr++;
        }
    printf("%d",Nr);
    return 0;
}