Cod sursa(job #1212854)

Utilizator andreas.chelsauAndreas Chelsau andreas.chelsau Data 26 iulie 2014 11:47:21
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
vector<int> l[100000 + 100];
int s[100000 + 100],N,M;
void add(int i,int j){
	if(i != j){
		l[i].push_back(j);
		l[j].push_back(i);
	}
}
void dfs(int node){
	vector<int> neighbours = l[node];
	s[node] = 1;
	for(int i = 0; i < neighbours.size(); i++){
		if(s[neighbours[i]] == 0){
			s[neighbours[i]] = 1;
			dfs(neighbours[i]);
		}
	}
}

int main(){
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i = 0; i < M; i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
	}
	int count = 0;
	for(int i = 1; i <= N; i++){
		if(s[i] == 0){
			dfs(i);
			count++;
		}
	}
	printf("%d\n",count);
	return 0;
}