Cod sursa(job #2134368)

Utilizator DimaTCDima Trubca DimaTC Data 17 februarie 2018 21:23:42
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<bits/stdc++.h>
#define NMAX 100010
using namespace std;

struct nod {
	int nr;
	nod* next;
};

typedef nod* lista;
lista lda[NMAX];
bool viz[NMAX];
int n,m,rs;
int x,y;
void add(int x, lista &p) {
	lista r = new nod({x,p});
	p=r;
}

void DFS(int x) {
	viz[x]=1;
	for (lista p=lda[x]; p; p=p->next) {
		if (!viz[p->nr]) {
			DFS(p->nr);
		}
	}
}


int main() {
	ifstream cin("dfs.in");
	ofstream cout("dfs.out");
	cin>>n>>m;
	
	for (int i=1; i<=m; i++) {
		cin>>x>>y;
		add(x, lda[y]);
		add(y, lda[x]);
	}
	
	for (int i=1; i<=n; i++) {
		if (!viz[i]) DFS(i), rs++;
	} cout<<rs;
	
	return 0;
}