Cod sursa(job #1950059)

Utilizator l-teenLucian l-teen Data 2 aprilie 2017 17:49:55
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
// DFSCompConexe.cpp : Defines the entry point for the console application.
//

#include <stdio.h>

int main(int argc, char* argv[])
{
	int nod[100000];
	unsigned int n, i, m, a, b, cc = 0;
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	scanf("%u %u", &n, &m);

	for (i = 0;i<n;++i)
		nod[i] = -1;

	for (i = 0; i< m;++i)
	{
		scanf("%u %u", &a, &b);
		--a;
		--b;
		if (nod[a] != -1)
			nod[b] = nod[a];
		else
		{
			if (nod[b] != -1)
				nod[a] = nod[b];
			else
			{
				nod[a] = cc;
				nod[b] = cc;
				++cc;
			}
		}
	}

	for (i = 0;i<n;++i)
		if (nod[i] == -1)
			cc += 1;

	printf("%u", cc);

	return 0;
}