Cod sursa(job #743224)

Utilizator osiceanu_paulOsiceanu paul osiceanu_paul Data 3 mai 2012 18:22:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<stdio.h>
#include<vector>
using namespace std;
const int N=1<<17;
int n,m;
bool viz[100001];
vector<int> a[N];


void citire()
{
	int x,y,i;
	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);
	}
}

void dfs(int x)
{
	int y;
	viz[x]=true;
	for(size_t i=0;i<a[x].size();i++)
	{
		y=a[x][i];
		if(!viz[y]) dfs(y);
	}
}

int main()
{
	int i,nr=0;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	
	
	citire();
	
	for(i=1;i<=n;i++)
		viz[i]=false;
	
	
	for(i=1;i<=n;i++)
		if(!viz[i]) 
			{
				dfs(i);
				nr++;
			}
	printf("%d ",nr);
}