Cod sursa(job #492613)

Utilizator proflaurianPanaete Adrian proflaurian Data 15 octombrie 2010 12:44:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<cstdio>
#include<vector>
using namespace std;
vector<int> v[100100];
int n,m,i,a,b,viz[100100];
void read(),solve(),DFS(int);
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(;m;m--)
	{
		scanf("%d%d",&a,&b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
}
void solve()
{
	for(m=0,i=1;i<=n;i++)
		if(!viz[i])
		{
			m++;DFS(i);
		}
	printf("%d\n",m);
}
void DFS(int N)
{
	vector<int>::iterator it;
	for(it=v[N].begin();it!=v[N].end();it++)
		if(!viz[*it])
		{
			viz[*it]=1;
			DFS(*it);
		}
}