Cod sursa(job #1231423)

Utilizator daniel.amarieiDaniel Amariei daniel.amariei Data 20 septembrie 2014 16:01:51
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
#include <bitset>
#include <list>

#define SIZE 1000001

using namespace std;

list<int>* ADJ[SIZE];
bitset<SIZE> V;


void dfs(int n)
{
	V.set(n);
	
	list<int>* neighbors = ADJ[n];
	if (neighbors)
	{
		for (list<int>::iterator it = neighbors->begin(); it != neighbors->end(); ++it)
		{
			if (!V.test(*it))
			{
				dfs(*it);
			}
		}
	}
}


int main()
{
	ifstream ifs("dfs.in");
	ofstream ofs("dfs.out");
	
	int n, m;
	ifs >> n >> m;

	for (int i = 0; i < m; ++i)	
	{
		int x, y;
		ifs >> x >> y;
		
		if(ADJ[x] == 00)
		{
			ADJ[x] = new list<int>();
		}

		if(ADJ[y] == 00)
		{
			ADJ[y] = new list<int>();
		}
		
		ADJ[x]->push_back(y);
		ADJ[y]->push_back(x);
	}
	
	int comp = 0;
	for (int i = 1; i <= n; ++i)	
	{
		if (!V.test(i))
		{
			dfs(i);
			++comp;
		}
	}
	
	ofs << comp;
}