Pagini recente » Cod sursa (job #2880143) | Cod sursa (job #1363684) | Clasament simulare_emag_mediu_2016_runda1 | Cod sursa (job #1731041) | Cod sursa (job #442753)
Cod sursa(job #442753)
#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;
}