Cod sursa(job #1508997)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 23 octombrie 2015 13:26:37
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>
#include <iostream>
using namespace std;

#define LE 100666

bool viz[LE];

struct nod
{
	int val;
	nod* next;
} ;

nod* H[LE];

void add(int xx,int yy)
{
	nod* P= new nod;
	P->val=yy;
	P->next=H[xx];
	H[xx]=P;
}

void dfs(int source)
{
	viz[source]=true;
	nod* V=H[source];

	for(;V!=NULL;V=V->next)
	  if (viz[V->val]==false)
	  	dfs(V->val);
}

ifstream f("wow.in");

int main()
{
    int n,m,i;
    f>>n>>m;

    for(i=1;i<=m;++i)
    {
    	int xx,yy;
    	f>>xx>>yy;
    	add(xx,yy);
    	add(yy,xx);
    }

    int result=0;

    for(i=1;i<=n;++i)
    	if (viz[i]==false)
    	{
    	    ++result;
            dfs(i);
        }

    cout<<result<<'\n';

	return 0;
}