Pagini recente » Cod sursa (job #1945035) | Cod sursa (job #591402) | Cod sursa (job #635361) | Cod sursa (job #3187243) | Cod sursa (job #1988208)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define file "dfs"
using VI = vector<int>;
using VVI = vector<VI>;
int n, m;
VVI g, C;
void read()
{
int x, y;
ifstream is(file".in", ios::in);
is >> n >> m;
g = VVI(n + 1);
for (int i = 1; i <= m; ++i)
{
is >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
is.close();
}
void solve()
{
VI comp, c(n + 1), p(n + 1), o(n + 1), N(n + 1);
int s = 1, i, j, E = 0;
while (E < n)
{
if (!p[s])
{
C.push_back(comp);
comp.clear();
comp.push_back(s);
p[s] = s;
o[s] = ++E;
i = s;
while (N[i] != g[i].size() || i != s)
if (N[i] == g[i].size())
i = p[i];
else
{
j = g[i][N[i]++];
if (!p[j])
{
p[j] = i;
i = j;
c[i] = C.size();
comp.push_back(i);
o[i] = ++E;
}
}
}
++s;
}
}
void write()
{
ofstream os(file".out", ios::out | ios::trunc);
os << C.size() << "\n";
/* for_each(C.begin(), C.end(), [&os](const VI& comp){
for_each(comp.begin(), comp.end(), [&os](int x){
os << x << " ";
});
os << "\n";
});*/
os.close();
}
int main()
{
read();
solve();
write();
return 0;
}