Cod sursa(job #1766407)

Utilizator wilson182Alexandrina Panfil wilson182 Data 27 septembrie 2016 22:01:31
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int m[N], c, v[N], n, u;
vector <int> lda[N];
void dfs(int nod)
{
	m[nod]=c;
	int i, j;
	for(i = 0; i<v[nod]; i++) if(m[lda[nod][i]] == 0) dfs(lda[nod][i]);
}
int main()
{
	int i, x, y;
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	scanf("%d %d", &n, &u);
	for(i = 0; i<u; i++){
		scanf("%d%d", &x, &y);
		lda[x].push_back(y);
		lda[y].push_back(x);
	}
	for (i = 1; i<=n; i++) v[i] = lda[i].size();
	memset(m, 0, n);
	c = 0;
	for (i = 1; i<=n; i++) if (m[i] == 0){
		c++;
		dfs(i);
	}
	printf("%d", c);
	return 0;
}