Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/bicudan | Statistici Mirea Radu (Geralt) | Istoria paginii utilizator/kcorflorin | Cod sursa (job #2815043)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define N 100001
using namespace std;
class Graph {
public:
vector <int> adiacenta[N];
bool visited[N];
int n_g, m_g;
vector <int> componente[N];
vector <int> solution;
void addEdge_neorientat(int h, int t);
void addEdge_orientat(int h, int t);
void BFS_mininum_distances(int root);
void DFS(int vf);
void SolveSortTop(int n_g, int m_g);
void Assign(int u, int root, vector<int> &conexitate);
void CTC();
void Solve_Conexe_DFS();
};
void Graph::addEdge_neorientat(int h,int t)
{
adiacenta[h].push_back(t);
adiacenta[t].push_back(h);
}
void Graph::addEdge_orientat(int h,int t)
{
adiacenta[h].push_back(t);
}
void Graph::DFS(int vf)
{
visited[vf] = true;
for(int i = 0; i < adiacenta[vf].size(); ++i)
if (!visited[adiacenta[vf][i]])
DFS(adiacenta[vf][i]);
solution.push_back(vf);
}
void Graph::Solve_Conexe_DFS()
{
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m, n1, n2, conexe = 0;
fin>>n>>m;
Graph g;
for (int i = 1; i <= m; i++)
{
fin >> n1 >> n2;
addEdge_neorientat(n1,n2);
}
for(int i = 1; i <= n; i++){
if (!visited[i])
{
conexe += 1;
DFS(i);
}
}
fout << conexe;
}
int main()
{
Graph g;
g.Solve_Conexe_DFS();
return 0;
}