Cod sursa(job #508342)

Utilizator paul992Cirstean Paul paul992 Data 8 decembrie 2010 00:24:23
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<stdio.h>
#include <algo.h> 
#include <vector> 
#define pb push_back
using namespace std;
vector <int> a[100001];
int n,m,c[100001];
bool viz[100001];
vector<int>::iterator it;

int bf(int x)
{int pi,ps;
pi=ps=1;
c[pi]=x;
viz[x]=true;
while(pi<=ps)
{x=c[pi];
for(it=a[x].begin();it!=a[x].end();it++)
	if(viz[*it]==false)
	{viz[*it]=true;
	c[++ps]=*it;}
	pi++;}
}






int main()
{freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
int x,y,nr=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{scanf("%d %d",&x,&y);
a[y].pb(x);
a[x].pb(y);}

for(int i=1;i<=n;i++)
if(viz[i]==false)
{nr++;
bf(i);}

printf("%d ",nr);
return 0;}