Pagini recente » Statistici Adi Florescu (adi.florescu) | Cod sursa (job #1774925) | Cod sursa (job #694750) | Cod sursa (job #83690) | Cod sursa (job #2425757)
// C++ program to print connected components in
// an undirected graph
#include<iostream>
#include <list>
#include <fstream>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
// Graph class represents a undirected graph
// using adjacency list representation
class Graph
{
int V; // No. of vertices
// Pointer to an array containing adjacency lists
list<int> *adj;
// A function used by DFS
void DFSUtil(int v, bool visited[]);
public:
Graph(int V); // Constructor
void addEdge(int v, int w);
void connectedComponents();
};
// Method to print connected components in an
// undirected graph
void Graph::connectedComponents()
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int v = 0; v < V; v++)
visited[v] = false;
int nr = 0;
for (int v=0; v<V; v++)
{
if (visited[v] == false)
{
// print all reachable vertices
// from v
DFSUtil(v, visited);
nr++;
}
}
out << nr << "\n";
}
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
if(!visited[*i])
DFSUtil(*i, visited);
}
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
// method to add an undirected edge
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
// Drive program to test above
int main()
{
int n;
in >> n;
// Create a graph given in the above diagram
Graph g(n); // 5 vertices numbered from 0 to 4
for(int i = 0; i < n; i++)
{
int x, y;
in >> x >> y;
g.addEdge(x, y);
}
g.connectedComponents();
return 0;
}