Cod sursa(job #1646538)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 10 martie 2016 16:33:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include <fstream>

using namespace std;
ifstream cin("dfs.in");
ofstream cout("dfs.out");

bool viz[100005];
int N, M, x, y, cnt;

typedef struct nod{
		int info;
		nod* next;
} *lnod;
lnod A[100005];

void add(lnod &a, int x){
		lnod b = new nod;
		b->info = x;
		b->next = a;
		a = b;
}

void dfs(int nodul){
	viz[nodul] = 1;
	for(lnod l = A[nodul]; l; l = l->next ) if(!viz[l -> info]) dfs(l->info);
	
}

int main(){
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		cin >> x >> y;
		add(A[x],y);
		add(A[y],x);
		}
	for(int i = 1; i <= N; i++){
		if(!viz[i]){ dfs(i);
		cnt++;}
		}
	cout << cnt;
	return 0;
}