Cod sursa(job #833895)

Utilizator alinaelenaFMI Colceag Alina alinaelena Data 13 decembrie 2012 11:38:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstdio>
#include <cstdlib>

const int maxn = 100010;

using namespace std;

int *G[maxn]; int deg[maxn], n, sol;
int visited[maxn];
void df(int node) {
	visited[node] = 1;
	for(int i = 0; i < deg[node]; ++i)
		if(!visited[G[node][i]])
			df(G[node][i]);
}
int main() {
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	
	int i, j, x, y, m;
	for( scanf("%d %d\n", &n, &m); m--; ) {
		scanf("%d %d", &i, &j);
		deg[i]++; deg[j]++;
	}
	fclose(stdin);
	for(int i = 1; i <= n; ++i) {
		G[i] = (int*)malloc(deg[i] * sizeof(int));
		deg[i] = 0;
	}
	
	freopen("dfs.in", "r", stdin);
	
	for( scanf("%d %d\n", &n, &m); m--; ) {
		scanf("%d %d", &x, &y);
		G[x][deg[x]] = y; G[y][deg[y]] = x;
		deg[x]++; ++deg[y];
	}
	
	for(int i = 1; i <= n; ++i)
		if(!visited[i])
			df(i), ++sol;
	printf("%d\n", sol);
}