Cod sursa(job #547374)

Utilizator stefynr8Space Monkey stefynr8 Data 6 martie 2011 12:02:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <cstdio>
#include <vector>

using namespace std;

vector <int> a[100005];


int n,m,viz[100005],h,x,y,ok,i;


void DFS(int nod)
{
	int j;
	viz[nod] = 1;
	for (j=0;j<a[nod].size();j++)
        if (!viz[a[nod][j]]) DFS(a[nod][j]);
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);

	for (i=1;i<=m;i++)
	{
	 scanf("%d %d",&x,&y);
     a[x].push_back(y);
     a[y].push_back(x);
	}


	for (i=1;i<=n;i++) if (!viz[i]) {
                                     h++;
                                     DFS(i);
                                     }

	printf("%d\n",h);
	return 0;
}