Cod sursa(job #2091260)

Utilizator Alex_AmarandeiAmarandei Matei Alexandru Alex_Amarandei Data 19 decembrie 2017 13:46:01
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");

int n, m, nr, start = 1;
bool f[100005];

vector <int> v;
vector <int> a[100005];

void read();
void DFS(int);
//void write();

int main()
{
	read();
	
	for (int i = 1; i <= n; i++)
	{
		if (!f[i])
		{
			DFS(i); nr++;
		}
	}

	fout << nr << '\n';

	//write();

	/*cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		v.push_back(x);
	}

	vector <int> :: iterator iv;

	for (iv = v.begin(); iv != v.end(); iv++)
		cout << *iv << ' ';*/

	return 0;
}

void read()
{
	int i, x, y;

	fin >> n >> m;

	for (i = 0; i < m; i++)
	{
		fin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
}

void DFS(int x)
{
	f[x] = true;

	for (int i = 0; i < a[x].size(); i++)
		if (!f[a[x][i]])
			DFS(a[x][i]);
}

/*void write()
{
	int i, x;

	for (x = 1; x <= n; x++)
	{
		for (i = 0; i < a[x].size(); i++)
			fout << a[x][i] << ' ';
		fout << '\n';
	}
}*/