Cod sursa(job #1221730)

Utilizator paulhermanPaul Herman paulherman Data 21 august 2014 13:05:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <cstdio>
#include <vector>
using namespace std;

const int MAX_V = 100005;
int V, E, vis[MAX_V], cc;
vector<int> adj[MAX_V];

void dfs(int u) {
	vis[u] = 1;
	for (int i = 0; i < (int)adj[u].size(); i++) {
		int v = adj[u][i];
		if (vis[v] == 0)
			dfs(v);
	}
}

int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	
	scanf("%d %d", &V, &E);
	for (int i = 0; i < E; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	cc = 0;
	for (int u = 1; u <= V; u++)
		if (vis[u] == 0)
			dfs(u), cc++;
			
	printf("%d\n", cc);
	
	return 0;
}