Pagini recente » Cod sursa (job #221186) | Cod sursa (job #3196088) | Cod sursa (job #2666696) | Cod sursa (job #532162) | Cod sursa (job #3158755)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
std::ifstream f("dfs.in");
std::ofstream g("dfs.out");
const int MAX_N = 10e3;
std::vector<std::vector<int>> listaAdiacenta(MAX_N + 1);
int vis[MAX_N + 1];
// construire lista adiacenta
void buildListaAdiacenta(int n, int m)
{
for (int i = 0; i <= n; ++i)
{
listaAdiacenta[i].clear();
}
for (int i = 0; i < m; i++)
{
int u, v;
f >> u >> v;
if (u != v)
{
listaAdiacenta[u].push_back(v);
listaAdiacenta[v].push_back(u);
}
}
}
// afisare lista adiacenta
void printListaAdiacenta(int n)
{
for (int i = 1; i <= n; i++)
{
std::cout << i << ": ";
for (int j = 0; j < listaAdiacenta[i].size(); j++)
{
std::cout << listaAdiacenta[i][j] << " ";
}
std::cout << "\n";
}
}
// dfs
void DFS(int x)
{
vis[x] = 1;
for (auto next : listaAdiacenta[x])
{
if (!vis[next])
DFS(next);
}
}
int main()
{
if (!f.is_open())
{
std::cerr << "Eroare deschidere fisier\n";
return 1;
}
int n, m;
f >> n >> m;
buildListaAdiacenta(n, m);
int nrComp = 0;
for (int i = 1; i <= n; i++)
{
if (!vis[i])
DFS(i), nrComp++;
}
g << nrComp;
return 0;
}