Cod sursa(job #528108)

Utilizator tudorsTudor Siminic tudors Data 1 februarie 2011 23:45:53
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <fstream>
#include <vector>
using namespace std;
const int N=100010;
vector <int> A[N];
int x,y,n,m;
int rez;
bool VIZ[N];

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

void dfs(int nod)
{
	VIZ[nod]=1;
	for (int j=0;j<A[nod].size();j++)
		if (!VIZ[A[nod][j]])
			dfs(A[nod][j]);
}

void citire()
{
	f>>n>>m;
	for (int i=1;i<=m;i++)
	{
		f>>x>>y;
		A[x].push_back(y);
		A[y].push_back(x);
	}
}

int main()
{
	citire();
	rez=0;
	for (int i=1;i<=n;i++)
		if (!VIZ[i])
		{
			dfs(i);
			rez++;
		}
	g<<rez;
	f.close();
	g.close();
	return 0;
}