Cod sursa(job #442753)

Utilizator tomescu_alinTomescu Alin tomescu_alin Data 15 aprilie 2010 09:05:32
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
using namespace std;

typedef unsigned long ulong;

#define NDEBUG

#ifdef NDEBUG
#define dbg	0 && (*((ostream *) 0))
#else
#define dbg clog
#endif

class ConnectedComponents
{
	public:
		ConnectedComponents(std::vector<std::vector<ulong>* >& adjacencyList, ulong nVertices, ulong nEdges)
			:	numVertices(nVertices), numEdges(nEdges), adjList(adjacencyList), count(0)
		{
			isVisited.resize(nVertices + 1, false);
		}
		
	public:
		void execute()
		{
			cout << "i = ";
			for(ulong i = 1; i <= numVertices; i++)
			{
				if(!isVisited[i])
				{
					cout << i << " ";
					dfs(i);
					count++;
				}
			}
		}
		
		void dfs(ulong node)
		{
			if(!isVisited[node])
			{
				isVisited[node] = true;
				
				if(adjList[node])
				{
					for(ulong i = 0; i < adjList[node]->size(); i++)
					{
						dfs((*adjList[node])[i]);
					}
				}
			}
		}
		
		
		ulong getCount() const { return count; }
		
	private:
		ulong numVertices;
		ulong numEdges;
		std::vector<std::vector<ulong>* >& adjList;
		ulong count;
		std::vector<bool> isVisited;
};

int main(int argc, char * argv[]) 
{
	
	const char * inFile = "dfs.in";
	const char * outFile = "dfs.out";
	
	ifstream fin(inFile);
	ofstream fout(outFile);
	
	#ifndef NDEBUG
		if(!fin || !fout) 
		{
			cerr << "Error opening one of \"" << inFile << "\" or \"" << outFile << "\"" << endl;
			return -1;
		}
	#endif
	
	/**
	 *	Read the data in.
	 */
	ulong n, m;
	fin >> n;
	fin >> m;
	
	std::vector<std::vector<ulong>* > adjList;
	adjList.resize(n + 1, NULL);
	
	ulong x, y;
	for(ulong i = 0; i < m; i++)
	{
		fin >> x;
		fin >> y;
		
		if(adjList[x] == NULL)
		{
			adjList[x] = new std::vector<ulong>();
		}
		
		if(adjList[y] == NULL)
		{
			adjList[y] = new std::vector<ulong>();
		}
		
		adjList[x]->push_back(y);
		adjList[y]->push_back(x);
	}
	
	/**
	 *	Solve the problem.
	 */
	ConnectedComponents cc(adjList, n, m);
	cc.execute();
	
	ulong count = cc.getCount(); 
	fout << count;
	
	/**
	 *	Cleanup!
	 */
	for(ulong i = 0; i < adjList.size(); i++)
	{
		if(adjList[i] != NULL)
			delete adjList[i];
	}
	
	fout.close();
	fin.close();
	
	return 0;
}