Cod sursa(job #837750)

Utilizator BalcauIonutFMI-Balcau Ionut BalcauIonut Data 18 decembrie 2012 17:01:25
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<fstream>
#include<vector>
using namespace std;

vector<int> v[100001];
bool ok[100001];
int count=0;
int s[100001];
void dfs(int x){
	int p=0,k;
	s[0]=x; ok[x]=true;
	vector<int>::iterator it;
	while(p>=0){
		k=s[p--];
		ok[k]=true;
		for(it=v[k].begin();it!=v[k].end();++it)
			if(!ok[*it]){
				s[++p]=*it;
			}
	}
}


int main(){
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n,m,x,y,i;
fin>>n>>m;

for(i=1;i<=m;++i){
	fin>>x>>y;
	v[x].push_back(y);
	v[y].push_back(x);
}

for(i=1;i<=n;++i)
	if(!ok[i]){
		count++;
		dfs(i);
	}

fout<<count;

}