Pagini recente » Cod sursa (job #2726952) | Cod sursa (job #2784404) | Cod sursa (job #2117051) | Cod sursa (job #313705) | Cod sursa (job #938841)
Cod sursa(job #938841)
#include <iostream>
#include <fstream>
using namespace std;
int N, M, solution;
int X, Y;
int dad[100100];
bool ap[100100];
inline int find(int X)
{
int _dad = X;
while (dad[X] != X) X = dad[X];
swap(_dad, X);
while (dad[X] != X)
{
int foo = dad[X];
dad[X] = _dad;
X = foo;
}
return _dad;
}
inline void join(int X, int Y)
{
dad[find(X)] = find(Y);
find(X); find(Y);
}
int main()
{
ifstream fin("dfs.in");
fin >> N >> M;
for (int i = 1; i <= N; i++)
dad[i] = i;
for (int i = 1; i <= M; i++)
{
fin >> X >> Y;
join(X, Y);
}
for (int i = 1; i <= N; i++)
ap[find(i)] = true;
for (int i = 1; i <= N; i++)
if (ap[i]) solution++;
ofstream fout("dfs.out");
fout << solution << '\n';
fin.close();
fout.close();
}