Pagini recente » Cod sursa (job #1095949) | Cod sursa (job #897433) | Cod sursa (job #1013713) | Cod sursa (job #2420246) | Cod sursa (job #2794767)
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
class Graph
{
int n; //nr de noduri
int m; //nr de muchii
vector<vector<int> > edges; //vector ce contine cate un vector cu vecini pt fiecare nod
bool oriented; // variabiabila pt a verifca daca e orientat
bool from1; // variabila pt a verifica daca nodurile sunt numerotate de la 1
public:
//constructori:
Graph(int, bool, bool);
Graph(int, int, bool, bool);
void insert_edge(int, int); //functie pt a insera muchii
vector<int> bfs(int); //functie pt a afla distantele minime de la un nod la celelate
int connected_comp(); //functie pt a afla nr de componente conexe
void dfs(int, vector<bool> &); //functie pt parcurgerea in adancime a unei componente
};
Graph::Graph(int n, bool oriented = false, bool from1 = false)
{
this->n = n;
m = 0;
this->from1 = from1;
this->oriented = oriented;
for (int i = 0; i < n; i++)
{
vector<int> aux;
edges.push_back(aux);
}
}
Graph::Graph(int n, int m, bool oriented = false, bool from1 = false)
{
this->n = n;
this->m = m;
this->from1 = from1;
this->oriented = oriented;
for (int i = 0; i < n; i++)
{
vector<int> aux;
edges.push_back(aux);
}
}
void Graph::insert_edge(int x, int y)
{
if (from1)
{
edges[x - 1].push_back(y - 1);
if (!oriented)
edges[y - 1].push_back(x - 1);
}
else
{
edges[x].push_back(y);
if (!oriented)
edges[y].push_back(x);
}
}
vector<int> Graph::bfs(int x)
{
vector<int> dist; //vector pt a memora distantele
queue<int> aux; //coada ce retine nodurile ce trebuie explorate
for (int i = 0; i < n; i++)
//nodurile nevizitate primesc distanta -1:
dist.push_back(-1);
if (from1)
x--;
aux.push(x);
dist[x] = 0;
while (!aux.empty())
{
for (int i = 0; i < edges[aux.front()].size(); i++)
{
//verificam daca nodurile vecine cu cel din varful cozii nu au fost vizitate:
if (dist[edges[aux.front()][i]] == -1)
{
//retinem distanta:
dist[edges[aux.front()][i]] = dist[aux.front()] + 1;
//adaugam nodul vizitat in coada:
aux.push(edges[aux.front()][i]);
}
}
//trecem la urmatorul nod ce trebuie explorat:
aux.pop();
}
return dist;
}
int Graph::connected_comp()
{
int nr = 0; //variabila pt a memora nr de componente conexe
vector<bool> visited; // vector care verifica daca nodurile au fost vizitate
for (int i = 0; i < n; i++)
visited.push_back(false);
for (int i = 0; i < n; i++)
{
if (visited[i] == false)
{
nr++;
//facem parcurgere in adancime pt a vizita toate nodurile componentei conexe:
dfs(i, visited);
}
}
return nr;
}
void Graph::dfs(int x, vector<bool> &visited)
{
visited[x] = true;
for (int i = 0; i < edges[x].size(); i++)
if (visited[edges[x][i]] == false)
dfs(edges[x][i], visited);
}
int main()
{
int n, m, a, b;
fin >> n >> m;
Graph g(n, m, false, true);
for (int i = 0; i < m; i++)
{
fin >> a >> b;
g.insert_edge(a, b);
}
fout << g.connected_comp();
}