Cod sursa(job #765636)

Utilizator vld7Campeanu Vlad vld7 Data 8 iulie 2012 15:26:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <cstdio>
#include <vector>

#define maxN 100005

using namespace std;

FILE *f = fopen ("dfs.in","r");
FILE *g = fopen ("dfs.out","w");

int n, m, sol, viz[maxN];
vector<int> L[maxN];

void read()
{
	fscanf (f, "%d%d", &n, &m);
	while (m--)
	{
		int a, b;
		
		fscanf (f, "%d%d", &a, &b);
		L[a].push_back(b);
		L[b].push_back(a);
	}
}

void df(int nod)
{
	viz[nod] = 1;
	for (int i = 0; i < L[nod].size(); i++)
		if ( !viz[ L[nod][i] ] )
			df(L[nod][i]);
}

int main()
{
	read();
	for (int i = 1; i <= n; i++)
		if ( !viz[i] )
		{
			sol++;
			df(i);
		}
		
	fprintf (g, "%d\n", sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}