Cod sursa(job #765739)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 9 iulie 2012 09:53:30
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#define nmax 100002
using namespace std;

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

bool Uz[nmax];
int N,M,K;

struct nod{
    int data;
    nod *next;
};
nod *V[nmax];

void Adauga_Muchie(int x,int y)
{
    nod *aux = new nod;
    aux->data = y;
    aux->next = V[x];
    V[x] = aux;
}

void DFS(int x)
{
    int y;
    Uz[x] = 1;
    nod *cont = new nod;
    for(cont = V[x];cont!=NULL;cont=cont->next)
    {
        y = cont->data;
        if(!Uz[y])
            DFS(y);
    }
}

int main()
{
    int x,y;
    in>>N>>M;
    while(M--)
    {
        in>>x>>y;
        Adauga_Muchie(x,y);
        Adauga_Muchie(y,x);
    }
    in.close();
    for(x=1;x<=N;x++)
        if(!Uz[x])
            K++,DFS(x);
    out<<K<<'\n';
    out.close();
    return 0;
}