Cod sursa(job #731109)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 7 aprilie 2012 15:07:52
Problema Parcurgere DFS - componente conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

vector<int> list[100005];
bool viz[100005];
queue<int> q;
void parcurge()
{
	while(q.size())
	{
		int urmnod=q.front();
		q.pop();
		viz[urmnod]=true;
		for(unsigned int i=0;i<list[urmnod].size();i++)
		{
			if(viz[list[urmnod][i]]==0)
				q.push(list[urmnod][i]);
		}
	}
	
}

int main()
{
	int n,m,nrc=0;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		list[x].push_back(y);
		list[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(viz[i]==0)
		{
			viz[i]=1;
			nrc++;
			for(unsigned int j=0;j<list[i].size();j++)
				q.push(list[i][j]);
			parcurge();
		}
	}
	printf("%d",nrc);
	
	return 0;
}