Pagini recente » Cod sursa (job #347070) | Cod sursa (job #2566442) | Cod sursa (job #837887) | Cod sursa (job #1512295) | Cod sursa (job #3249418)
#include <iostream>
#include <queue>
#include <list>
#include <fstream>
#include <unordered_set>
#include <cstring>
#include <stdio.h>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
struct nod
{
int cost = -1;
list <int> p;
}el[100005];
bool frecventa[100005];
void crearelista(nod el[], int n, int m,bool ordonat)
{
int x1, x2;
for (int i = 1; i <= m; i++)
{
in >> x1 >> x2;
el[x1].p.push_back(x2);
if (ordonat == 0)
el[x2].p.push_back(x1);
}
}
void afisarelista(nod el[], int n)
{
for (int i = 1; i <= n; i++)
{
out << "Nodul " << i << " duce la urmatoarele noduri:" << '\n';
for (auto p = el[i].p.begin(); p != el[i].p.end(); p++)
out << *p << ' ';
out << '\n';
}
}
void clear(queue <int>& q1)
{
std::queue<int> emp;
swap(q1, emp);
};
void DFS(nod el[], queue <int> q1)
{
while (!q1.empty())
{
auto i = q1.front();
//std::cout << i;
q1.pop();
frecventa[i] = 1;
for (auto t = el[i].p.begin(); t != el[i].p.end(); t++)
{
q1.push(*t);
}
};
}
int main()
{
int n, m, s,px;
in >> n >> m;
crearelista(el, n, m, 1);
queue <int> q1;
int cnt = 0;
for (int i = 1; i <= n; i++)
{
if (frecventa[i] == 0)
{
cnt++;
q1.push(i);
DFS(el, q1);
}
}
out << cnt;
}