Cod sursa(job #407898)

Utilizator xtephanFodor Stefan xtephan Data 2 martie 2010 18:28:58
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#include<vector>

using namespace std;

long cc,n,m;
bool viz[100010];
vector<int> Graf[100010];

void cit();
void rez();
void afis();

int main() {
	
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	
	cit();
	rez();
	afis();
	
	return 0;
}


void cit() {
	scanf("%ld%ld", &n, &m);
	for(long i=1; i<=m; i++) {
		int x,y;
		scanf("%d%d", &x, &y);
		Graf[x].push_back(y);
		Graf[y].push_back(x);
	}
}

void dfs(int k) {
	
	viz[k]=1;
	
	/*
	vector<int>::iterator it;
	
	for(it=Graf[i].begin(); it!=Graf[i].end();  ++it) {
		if( !viz[ Graf[i][*it] ] ) {
			viz[ Graf[i][*it] ]=1;
			dfs( Graf[i][*it] );
		}
	}
	*/
	
	for(int i=0; i<(int)Graf[k].size();  ++i) {
		if( !viz[ Graf[k][i] ] ) {
			dfs( Graf[k][i] );
		}
	}
	
}


void rez() {
	
	for(long i=1; i<=n;i++) 
		if(!viz[i]) {
			cc++;
			dfs(i);
		}
	
}


void afis() {
	printf("%ld",cc);
}