Pagini recente » Cod sursa (job #3152321) | Cod sursa (job #1436529) | Cod sursa (job #709406) | Cod sursa (job #667627) | Cod sursa (job #938836)
Cod sursa(job #938836)
#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 dd = X;
while (dad[X] != X) X = dad[X];
swap(dd, X);
while (dad[X] != X)
{
int foo = dad[X];
dad[X] = dd;
X = foo;
}
}
inline void join(int X, int Y)
{
dad[dad[X]] = dad[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[dad[i]] = true;
for (int i = 1; i <= N; i++)
if (ap[i]) solution++;
ofstream fout("dfs.out");
fout << solution << '\n';
fin.close();
fout.close();
}