Cod sursa(job #395087)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 12 februarie 2010 08:27:04
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <vector>
#include <stdio.h>
#define NMAX 100001
using namespace std;
int N,M,NR;
vector <int> C[NMAX];
int viz[NMAX];

void citire()
{
	FILE *fin=fopen("dfs.in","r");
	fscanf(fin,"%d %d",&N,&M);
	int i,x,y;
	
	for(i=1;i<=M;i++)
	{
		fscanf(fin,"%d %d",&x,&y);
		
		C[x].push_back(y);
		C[y].push_back(x);
		
	}

fclose(fin);	
}

void dfs(int x)
{	int i;	
	viz[x]=1;
	for(i=0;i<C[x].size();i++)
	{if (viz[C[x][i]]==0)	
				dfs(C[x][i]);
	}
	
	
	
}




int main()
{
	citire();
	int i=1;
	for(i=1;i<=N;i++)
		{
			if (viz[i]==0) {NR++;dfs(i);}
		}	
	FILE *fout=fopen("dfs.out","w");
	fprintf(fout,"%d\n",NR);
	fclose(fout);
		
}