Pagini recente » Cod sursa (job #2709390) | Cod sursa (job #268577) | Cod sursa (job #677973) | Cod sursa (job #176758) | Cod sursa (job #1546956)
#include <fstream>
#include <list>
class Graph {
int V;
int comp;
std::list<int> *adj;
void DFSUtil(int v, bool visited[]);
public:
Graph(int V);
int getComp();
void addEdge(int, int);
void DFS();
};
Graph::Graph(int V)
{
this->V = V;
comp = 0;
adj = new std::list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
}
void Graph::DFSUtil(int v, bool visited[])
{
visited[v] = true;
for (std::list<int>::iterator i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
void Graph::DFS()
{
bool *visited = new bool[V];
for (int i = 0; i < V; ++i)
visited[i] = false;
for (int i = 0; i < V; ++i)
if (!visited[i]) {
DFSUtil(i, visited);
comp++;
}
}
int Graph::getComp()
{
return comp;
}
int main(int argc, char **argv)
{
std::ifstream input("dfs.in");
std::ofstream output("dfs.out");
int N, M;
input >> N >> M;
Graph g(N);
for (int i = 0; i < M; ++i) {
int x, y;
input >> x >> y;
g.addEdge(x, y);
}
g.DFS();
output << g.getComp() << std::endl;
input.close();
output.close();
return 0;
}