Cod sursa(job #672270)

Utilizator pykhNeagoe Alexandru pykh Data 1 februarie 2012 20:14:03
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<cstdio>
#include<vector>
using namespace std;

const char in[]="dfs.in";
const char out[]="dfs.out";

const int N = 100005;

vector<int>G[N];

int ok[N], sol, n, m, x ,y;

void dfs(int x)
	{
		ok[x] = true;
		for(int i = 0 ; i < G[x].size() ; ++i)
			if(!ok[ G[ x ][ i ] ])dfs(G[x][i]);
}

int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w",stdout);
		
		scanf("%d %d", &n, &m);
		
		for(int i = 1 ; i <= m ; ++i)
		{
			scanf("%d %d", &x, &y);
			G[x].push_back(y);
			G[y].push_back(x);
		}
		
		for(int i = 1 ; i <= n ; ++i)
			if(!ok[i])dfs(i), ++sol;
		
		printf("%d\n", sol);
			
	return 0;
}