Pagini recente » Clasament simulare_oji_2023_clasele_11_12_14_martiee | Cod sursa (job #2425126) | Cod sursa (job #153140) | Cod sursa (job #620396) | Cod sursa (job #846521)
Cod sursa(job #846521)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N, M, sol, lu[100100];
bool ap[100100];
vector<int> A[100100];
stack<int> S;
void DFs(int i)
{
S.push(i);
ap[i] = true;
while (!S.empty())
{
int nod = S.top();
while (lu[nod] < A[nod].size() && ap[A[nod][lu[nod]]]) ++lu[nod];
if (lu[nod] < (int)A[nod].size())
{
int var = A[nod][lu[nod]];
++lu[nod];
S.push(var);
ap[var] = true;
}
else
{
S.pop();
}
}
++sol;
}
int main()
{
fin >> N >> M;
for (int i = 1; i <= M; ++i)
{
int x, y;
fin >> x >> y;
A[x].push_back(y);
A[y].push_back(x);
}
for (int i = 1; i <= N; ++i)
{
if (!ap[i])
{
DFs(i);
}
}
fout << sol << '\n';
fout.close();
return 0;
}