Cod sursa(job #766470)

Utilizator alex_ovidiunituAlex Ovidiu Nitu alex_ovidiunitu Data 11 iulie 2012 14:18:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
#include<bitset>
using namespace std;
int n,m,x,y,conex;
vector <int > a[100001];
bool apar[100001];
void DFS(int nod)
{
	//stack <int> s;
	//s.push(nod);
	apar[nod]=1;
	int i;
	for(i=0;i<a[nod].size();++i)
	{
		
		if (!apar[a[nod][i]])
			DFS(a[nod][i]);
	}
}
int main(void)
{
	fstream f,g;
	f.open("dfs.in",ios::in);
	g.open("dfs.out",ios::out);
	f>>n>>m;
	int i;
	for (i=1;i<=m;i++)
	{
		f>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	DFS(1);
	conex++;
	int ok=0;
	while (ok==0)
	{
		ok=1;
		for (i=1;i<=n;++i)
			if (apar[i]==0)
				{
					DFS(i);
					ok=0;
					conex++;
				}
	}
	g<<conex;
}