Cod sursa(job #2425757)

Utilizator MikeVMihai Vasilescu MikeV Data 25 mai 2019 00:44:35
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
// 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;
}