Cod sursa(job #1217142)

Utilizator pavlov.ionPavlov Ion pavlov.ion Data 6 august 2014 18:46:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define MAXN 100005
#define pb push_back
using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");
int N,M;
char viz[MAXN];
vector<int> G[MAXN];
void DFS(int x) {
	 int i;
	 for(i=0;i<G[x].size();i++)
	     if(!viz[G[x][i]]) {
		 				   viz[G[x][i]]=1;
					       DFS(G[x][i]); }
}
int main() {
	int i,j,x,y,k=0;
	cin>>N>>M;
	for(i=1;i<=M;i++) {
	           cin>>x>>y;
	           G[x].pb(y);
	           G[y].pb(x); }
	for(i=1;i<=N;i++)
	           if(!viz[i]) { k++;
			                 DFS(i); }
	cout<<k;
	return 0;
}