Cod sursa(job #904239)

Utilizator PregatireONIAnamaria Cotirlea PregatireONI Data 3 martie 2013 22:37:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include<stdio.h>
#include <vector>

using namespace std;

FILE *f,*s;

int m,n,i,j,k;

vector <int> v1[100005];

int v2[100005];

void DFS(int k)
{
	v2[k]=1;
	
	for(int i=0;i<v1[k].size();i++)
		if(!v2[v1[k][i]]) DFS(v1[k][i]);
}

int main()
{
	f=fopen("dfs.in","r");
	s=fopen("dfs.out","w");
	
	fscanf(f,"%d %d",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		int a,b;
		
		fscanf(f,"%d %d",&a,&b);

		v1[a].push_back(b);
		v1[b].push_back(a);
	}
	
	for(i=1;i<=n;i++)
	{
		if(!v2[i])
		{
			DFS(i);
			
			k++;
		}	
	}
	
	fprintf(s,"%d",k);
	
	fclose(s);
	
	return 0;
}