Pagini recente » Cod sursa (job #751179) | Cod sursa (job #1713120) | Cod sursa (job #2279570) | Cod sursa (job #2899552) | Cod sursa (job #2819783)
#include <fstream>
#include <vector>
#define NMAX 100005
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
bool frecvvec[NMAX];
bool frecvrand[NMAX];
int father[NMAX];
vector <int> vec[NMAX];
int main()
{
int n, m, i, j, a, b, k = 0, gigel = 0;
in >> n >> m;
for (j = 1; j <= m; ++j)
{
in >> a >> b;
if (father[a] == 0 && father[b] == 0)
{
++k;
father[a] = k;
father[b] = k;
vec[k].push_back(a);
vec[k].push_back(b);
}
else if (father[a] != 0 && father[b] == 0)
{
father[b] = father[a];
vec[father[b]].push_back(b);
}
else if (father[a] == 0 && father[b] != 0)
{
father[a] = father[b];
vec[father[a]].push_back(a);
}
else if (father[a] != 0 && father[b] != 0)
{
for (i = 0; i < vec[father[b]].size(); ++i)
{
father[vec[father[b]][j]] = father[a];
vec[father[a]].push_back(vec[father[b]][j]);
}
frecvrand[father[b]] = 1;
}
}
for (j = 1; j <= k; ++j)
{
if (frecvrand[j] == 0)
{
++gigel;
for (i = 0; i < vec[j].size(); ++i)
{
frecvvec[vec[j][i]] = 1;
}
}
}
for (i = 1; i <= n; ++i)
{
if (frecvvec[i] == 0)
++gigel;
}
out << gigel;
return 0;
}