Cod sursa(job #938456)

Utilizator PsychoRoAlex Buicescu PsychoRo Data 12 aprilie 2013 17:38:05
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.15 kb
#include <iostream>
#include <fstream>
#include <vector>

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

struct vertex
{
	int index;
	vertex *next;
};
vertex *liste[100000];

int n, m, a[100][100], v[100000];

void citireMatrice()
{
	int i, j;
	fin>>n>>m;
	while(fin>>i>>j)
	{
		a[i][j] = a[j][i] = 1;
	}
}

void dfMatrice(int k)
{
	for(int i = 1 ; i <= n ; i++)
	{
		if(a[i][k] == 1 && !v[i])
		{
			std::cout<<i<<" ";
			v[i] = 1;
			dfMatrice(i);
		}
	}
}

void bfMatrice(int k)
{
	std::vector<int> vec;
	vec.push_back(k);

	while(vec.size())
	{
		for(int i = 1 ; i <= n ; i ++)
		{
			if(a[vec.front()][i] == 1 && !v[i])
			{
				a[vec.front()][i] = a[i][vec.front()] = 2;
				std::cout<<i<<' ';
				v[i] = 1;
				vec.push_back(i);
			}
		}
		vec.erase(vec.begin());
	}
}


void citireListe()
{
	int i, j;
	fin>>n>>m;
	while(fin>>i>>j)
	{
		vertex *newVex = new vertex;
		newVex->index = j;
		newVex->next = liste[i];
		liste[i] = newVex;

		vertex *newVex2 = new vertex;
		newVex2->index = i;
		newVex2->next = liste[j];
		liste[j] = newVex2;
	}
}

void dfListe(int k)
{
	vertex *p = liste[k];
	while(p)
	{
		if(!v[p->index])
		{
			//std::cout<<p->index<<" ";
			v[p->index] = 1;
			dfListe(p->index);
		}
		p = p->next;
	}
	delete p;
}

void bfListe(int k)
{
	std::vector<int> vec;
	vec.push_back(k);

	while(vec.size())
	{
		vertex *p = liste[vec.front()];
		while(p)
		{
			if(!v[p->index])
			{
				v[p->index] = 1;
				vec.push_back(p->index);
				std::cout<<p->index<<" ";
			}
			p = p->next;
		}
		delete p;
		vec.erase(vec.begin());
	}
}


int main()
{
	/*
	citireListe();
	std::cout<<1<<" ";
	v[1] = 1;
	bfListe(1);*/

	citireListe();
	int nrTot = 0;
	for(int i = 1; i <= n ; i++)
	{
		if(!v[i])
		{
			nrTot++;
			dfListe(i);
		}
	}
	std::cout<<nrTot;
/*
	std::cout<<'\n'<<'\n';
	for(int i = 1; i <= n ;i++)
	{
		std::cout<<i<<": ";
		vertex *p = liste[i];
		while(p)
		{
			std::cout<<p->index<<" ";
			p = p->next;
		}
		delete p;
		std::cout<<'\n';
	}*/

    //cout << "Hello world!" << '\n';
    return 0;
}