Cod sursa(job #2310359)

Utilizator The_one_and_onlyMironica Vasile The_one_and_only Data 31 decembrie 2018 13:09:00
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
using namespace std;

ofstream cout("dfs.out");
ifstream cin("dfs.in");
int n, m, viz[100005], k;

typedef struct nod {
	int x;
	nod *a;
} *pNod;
pNod v[100005];

void add(pNod &dest, int val) {
	pNod p;
	p=new nod;
	p->x=val;
	p->a=dest;
	dest=p;
}

void DFS(int nod) {
	pNod p;
	viz[nod]=1;
	for(p=v[nod]; p!=NULL; p=p->a)
		if(!viz[p->x])
			DFS(p->x);
}

int main() {
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		int x, y;
		cin>>x>>y;
		add(v[x], y);
		add(v[y], x);
	}
	for(int i=1; i<=n; i++)
		if(!viz[i])
			k++, DFS(i);
	cout<<k;
	return 0;
}