Cod sursa(job #792165)

Utilizator Alexxino7Alexandru Popescu Alexxino7 Data 26 septembrie 2012 17:33:33
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;
#define Maxim 100004
typedef unsigned int uint;

ifstream fin("dfs.in");
ofstream fout("dfs.out");

int N,M,sol,viz[Maxim];
vector<int> G[Maxim];

void dfs(int x){
	viz[x]=1;
	
	for(uint i=0;i<G[x].size();i++){
		if(!viz[G[x][i]])
			dfs(G[x][i]);
	}
}

int main(){
	
	fin>>N>>M;
	
	int x,y;
	for(int i=1;i<=M;i++){
		fin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	
	for(int i=1;i<=N;i++){
		if(!viz[i]){
			sol++;
			dfs(i);
		}
	}
	
	fout<<sol<<"\n";
	
	fin.close();
	fout.close();
	return 0;
}