Pagini recente » Cod sursa (job #1747519) | Cod sursa (job #241594) | Cod sursa (job #3129737) | Cod sursa (job #2084773) | Cod sursa (job #2786585)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graph
{
int NumberOfNodes;
int NumberOfEdges;
bool Oriented;
vector<vector<int>> AdjacencyList;
public:
Graph();
Graph(int, int, bool);
void Build();
void BFS(int, int[]);
void DFS(int, bool[]);
int NumberOfConnectedComponents();
};
int main()
{
int NumberOfNodes, NumberOfEdges;
fin >> NumberOfNodes >> NumberOfEdges;
Graph G(NumberOfNodes, NumberOfEdges, 0);
G.Build();
fout << G.NumberOfConnectedComponents();
/* ----------------------------BFS----------------------------
int NumberOfNodes, NumberOfEdges, StartNode;
fin >> NumberOfNodes >> NumberOfEdges >> StartNode;
Graph G(NumberOfNodes, NumberOfEdges, true);
G.Build();
int Distance[NumberOfNodes];
StartNode--;
G.BFS(StartNode, Distance);
for (int i = 0; i < NumberOfNodes; i++)
fout << Distance[i] << " ";
----------------------------BFS----------------------------*/
fin.close();
fout.close();
return 0;
}
Graph::Graph() : NumberOfNodes(0), NumberOfEdges(0), Oriented(0) { }
Graph::Graph(int _NumberOfNodes, int _NumberOfEdges, bool _Oriented) : NumberOfNodes(_NumberOfNodes), NumberOfEdges(_NumberOfEdges), Oriented(_Oriented)
{
NumberOfNodes = _NumberOfNodes;
NumberOfEdges = _NumberOfEdges;
Oriented = _Oriented;
for (int i = 0; i < _NumberOfNodes; i++)
AdjacencyList.push_back( {} );
//AdjacencyList.push_back(vector<int>());
}
void Graph::Build()
{
for (int i = 0; i < NumberOfEdges; i++)
{
int FirstNode, SecondNode;
fin >> FirstNode >> SecondNode;
FirstNode--;
SecondNode--;
AdjacencyList[FirstNode].push_back(SecondNode);
if (!Oriented)
AdjacencyList[SecondNode].push_back(FirstNode);
}
}
void Graph::BFS(int StartNode, int Distance[])
{
bool Visited[NumberOfNodes];
queue<int> BFSQueue;
for(int i = 0; i < NumberOfNodes; i++)
{
Visited[i] = 0;
Distance[i] = -1;
}
Visited[StartNode] = 1;
Distance[StartNode] = 0;
BFSQueue.push(StartNode);
while (!BFSQueue.empty())
{
int CurrentNode = BFSQueue.front();
for (unsigned int i = 0; i < AdjacencyList[CurrentNode].size(); i++)
{
int AdjacentNode = AdjacencyList[CurrentNode][i];
if (!Visited[AdjacentNode])
{
Visited[AdjacentNode] = 1;
Distance[AdjacentNode] = Distance[CurrentNode] + 1;
BFSQueue.push(AdjacentNode);
}
}
BFSQueue.pop();
}
}
void Graph::DFS(int StartNode, bool Visited[])
{
Visited[StartNode] = 1;
for (unsigned int i = 0; i < AdjacencyList[StartNode].size(); i++) //parcurg vecinii nodului
{
int NextNode = AdjacencyList[StartNode][i];
if (!Visited[NextNode])
DFS(NextNode, Visited);
}
}
int Graph::NumberOfConnectedComponents()
{
bool Visited[NumberOfNodes];
int _NumberOfConnectedComponents = 0;
for (int i = 0; i < NumberOfNodes; i++)
Visited[i] = 0;
for (int i = 0; i < NumberOfNodes; i++)
{
if (!Visited[i])
{
DFS(i, Visited);
_NumberOfConnectedComponents++;
}
}
return _NumberOfConnectedComponents;
}