Pagini recente » Cod sursa (job #2145833) | Cod sursa (job #2106683) | Cod sursa (job #1908757) | Cod sursa (job #1337107) | Cod sursa (job #938837)
Cod sursa(job #938837)
#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[X] = 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(find(X), find(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();
}