Cod sursa(job #1076587)

Utilizator anaid96Nasue Diana anaid96 Data 10 ianuarie 2014 13:20:48
Problema Parcurgere DFS - componente conexe Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<stdio.h>
#include<vector>
#define Nmax 1000001
FILE *in,*out;

using namespace std;

int n,m,x,y;
int nrc;
bool viz[Nmax];
vector<int> graf[Nmax];
void dfs(int nod);

int main(void)
{
	in=fopen("dfs.in","rt");
	out=fopen("dfs.out","wt");
	fscanf(in,"%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		fscanf(in,"%d%d",&x,&y);
		graf[x].push_back(y);
		graf[y].push_back(x);
	}	
	for(int i=1;i<=n;++i)
	{
		if(!viz[i])
		{
			nrc++;
			viz[i]=true;
			dfs(i);
		}	
	}	
	fprintf(out,"%d",nrc);
	
}	

void dfs(int nod)
{
	vector<int>::iterator it, end=graf[nod].end();
	for(it=graf[nod].begin() ; it!=end ; ++it)
	{
		if(!viz[*it])
		{
			viz[*it]=true;
			dfs(*it);
		}	
	}	
}