Cod sursa(job #1331623)

Utilizator andreiulianAndrei andreiulian Data 31 ianuarie 2015 21:09:15
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<iostream>
#include<fstream>
#include<vector>
#define pb push_back
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int N,M,s[100005],u,r;
bool viz[100005];
vector<int> v[100005];
void df(int i);
int main()
{
	in>>N>>M;
	int i,a,b;
	for(i=1;i<=N;++i) v[i].pb(0);
	for(i=1;i<=M;++i)
	{
		in>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
		v[a][0]++;
		v[b][0]++;
	}
	for(i=1;i<=N;++i)
	{
		if(!viz[i]) df(i),++r;
	}
	out<<r<<'\n';
}
void df(int i)
{
	s[++u]=i;
	viz[i]=1;
	int k,c,cont;
	while(u)
	{
		c=s[u];
		cont=0;
		for(k=1;k<=v[c][0];++k)
		{
			if(!viz[v[c][k]])
				s[++u]=v[c][k],cont=1,viz[v[c][k]]=1;;
		}
		if(cont==0) u--;
	}
}