Cod sursa(job #435549)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 7 aprilie 2010 16:35:40
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <cstdio>
#include <vector>
using namespace std;

const int N = 100001;

int n;
vector<int> vecin[N];
bool vizitat[N];

void citire()
{
	int a,b,m;
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= m; ++i)
	{
		scanf("%d%d",&a,&b);
		vecin[a].push_back(b);
	}
}

void explorare(int poz)
{
	vizitat[poz] = true;
	for (int i = 0; i < vecin[poz].size(); ++i)
		explorare(vecin[poz][i]);
}

int numar_de_insule()
{
	int nri = 0;
	for (int i = 1; i <= n; ++i)
		if (!vizitat[i])
		{
			++nri;
			explorare(i);
		}
	return nri;
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	citire();
	printf("%d",numar_de_insule());
	return 0;
}