Pagini recente » Cod sursa (job #24050) | Cod sursa (job #1140115) | Cod sursa (job #1469279) | Cod sursa (job #2745442) | Cod sursa (job #2795982)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graph
{
private:
int verticesNo;
int edgesNo;
bool oriented;
vector<vector<int>> adjacencyList;
public:
Graph();
Graph(int verticesNo, int edgesNo, bool oriented);
void bfs(int start);
void dfs(int vertex, vector<int> &visited);
int connectedComponentsNo();
virtual ~Graph();
};
Graph::Graph()
{
verticesNo = edgesNo = oriented = 0;
this->adjacencyList.clear();
}
Graph::Graph(int verticesNo, int edgesNo, bool oriented)
{
this->verticesNo = verticesNo;
this->edgesNo = edgesNo;
this->oriented = oriented;
this->adjacencyList.resize(verticesNo + 1);
int vertex1, vertex2;
for(int i = 0; i < this->edgesNo; i++)
{
fin>>vertex1>>vertex2;
this->adjacencyList[vertex1].push_back(vertex2);
if(this->oriented == 0)
this->adjacencyList[vertex2].push_back(vertex1);
}
}
Graph::~Graph()
{
this->adjacencyList.clear();
}
void Graph::bfs(int start)
{
int n = this->verticesNo;
vector<int> visited;
vector<int> distances;
queue<int> order;
order.push(start);
for(int i = 0; i <= n; i++)
{
visited.push_back(0);
distances.push_back(-1);
}
distances[start] = 0;
visited[start] = 1;
while(!order.empty())
{
int current = order.front();
int sz = adjacencyList[current].size();
order.pop();
for(int i = 0; i < sz; i++)
{
int temp = adjacencyList[current][i];
if(visited[temp] == 0)
{
visited[temp] = 1;
order.push(temp);
distances[temp] = distances[current]+1;
}
}
}
for(int i = 1; i < distances.size(); i++)
fout<<distances[i]<<" ";
}
void Graph::dfs(int vertex, vector<int> &visited)
{
visited[vertex] = 1;
int sz = adjacencyList[vertex].size();
for(int i = 0; i < sz; i++)
{
if(visited[adjacencyList[vertex][i]] == 0)
dfs(adjacencyList[vertex][i],visited);
}
}
int Graph::connectedComponentsNo()
{
vector<int> visited;
int ccn = 0; //no of connected components
for(int i = 0 ; i <= this->verticesNo; i++)
visited.push_back(0);
for(int i = 1; i <= this->verticesNo; i++)
if(visited[i] == 0)
{
dfs(i,visited);
ccn++;
}
return ccn;
}
int main()
{
int N,M;
fin>>N>>M;
Graph df(N,M,0);
fout<<df.connectedComponentsNo();
return 0;
}