Pagini recente » Cod sursa (job #154875) | Cod sursa (job #1526918) | Cod sursa (job #525938) | Cod sursa (job #2644396) | Cod sursa (job #2715212)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
const int nMax = 100000 + 5;
vector < int > l[nMax];
stack < int > stk;
bitset < nMax > vis;
int n, m;
int componente = 0;
void Citire()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
int a, b;
fin >> a >> b;
l[a].push_back(b);
l[b].push_back(a);
}
}
void Afisare()
{
fout << componente;
}
void Dfs(int nod)
{
stk.push(nod);
vis[nod] = 1;
while (!stk.empty())
{
nod = stk.top();
stk.pop();
for (int next : l[nod])
{
if (!vis[next])
{
stk.push(next);
vis[next] = 1;
}
}
}
}
void Rezolvare()
{
for (int i = 1; i <= n; i++)
{
if (!vis[i])
{
Dfs(i);
componente++;
}
}
}
int main()
{
Citire();
Rezolvare();
Afisare();
fin.close();
fout.close();
return 0;
}