Cod sursa(job #885091)

Utilizator b_ady20Branescu Adrian b_ady20 Data 21 februarie 2013 17:20:39
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<cstdio>
#include<vector>
using namespace std;
#define mata vector< vector<int> >
int n,m;
mata list(void){
	int i,x,y;
	vector< vector<int> >v(n+1);
	for(i=0;i<m;++i){
		scanf("%d%d",&x,&y);
		v[x].push_back(y); v[y].push_back(x);
	}
	return v;
}
bool found(mata l,int where,int tofind){
	vector<int>::iterator it;
	for(it=l[where].begin();it!=l[where].end();++it)
		if(*it==tofind) return 1;
	return 0;
}
void df(mata l,int nod,int viz[]){
	int i;
	viz[nod]=1;
	for(i=1;i<n;++i)
		if(!viz[i]&&found(l,nod,i)) df(l,i,viz);
}
int main(){
	int i,viz[100000]={0},cont=0;
	mata lista;
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&n,&m);
	lista=list();
	for(i=1;i<=n;++i)
		if(!viz[i]){
			df(lista,i,viz);
			++cont;
		}
	printf("%d\n",cont);
	return 0;
}