Cod sursa(job #2329514)

Utilizator psa2001Pascaru Stefan-Alin psa2001 Data 26 ianuarie 2019 20:57:57
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("dfs.in");
ofstream out("dfs.out");

const int nl=100005;
bool nv[nl];
int n,m,suba=0;

vector <int> muchii[nl];

void DFS(int nod)
{
	nv[nod]=true;
	for(unsigned int i= 0; i<muchii[nod].size(); i++)
	{
		int vecin = muchii[nod][i];
		if(!nv[vecin])
			DFS(vecin);
	}
}

void citire()
{
	in>>n>>m;
	for(int i=1; i<=m;i++)
	{
		int x ,y;
		in>>x>>y;
		muchii[x].push_back(y);
		muchii[y].push_back(x);
	}
	for(int i=1; i<=n; i++)
	{
		if(!nv[i])
		{
			suba+=1;
			DFS(i);
		}
	}
}

int main() 
{	

	citire();
	out<<suba;
	return 0;
}