Cod sursa(job #755335)

Utilizator roxyroxy2011Luca Roxana roxyroxy2011 Data 5 iunie 2012 14:46:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("dfs.in");
ofstream g("dfs.out");

vector<int>a[100001];
int n,m,viz[100001],sol;

void read();
void solve(int);

int main()
{
	read();
	for (int i=1;i<=n;i++)
		if (!viz[i]){solve(i);sol++;}
	g<<sol<<'\n';
	f.close();g.close();
	return 0;
}

void read()
{
	f>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int l,c;f>>l>>c;
		a[l].push_back(c);
		a[c].push_back(l);
	}
}

void solve(int p)
{
	queue <int> que;
	que.push(p);viz[p]=1;
	while (!que.empty())
	{
		int aux=que.front();que.pop();
		for (int i=0;i<a[aux].size();i++)
		if (!viz[a[aux][i]])
		{
			viz[a[aux][i]]=1;
			que.push(a[aux][i]);
		}
	}
}