Pagini recente » Cod sursa (job #1561129) | Cod sursa (job #106578) | Cod sursa (job #3153387) | Cod sursa (job #3133491) | Cod sursa (job #372569)
Cod sursa(job #372569)
# include <fstream>
using namespace std;
int n, m, t[100003], nrc, h[100003];
int rad (int x)
{
while (t[x]) x=t[x];
return x;
}
void reuniune (int x, int y)
{
int rx, ry;
rx=rad(x);
ry=rad(y);
if (rx!=ry)
{
nrc--;
if (h[rx]>h[ry])
t[ry]=rx;
else
if (h[rx]<h[ry])
t[rx]=ry;
else
t[rx]=ry, h[ry]++;
}
}
int main ()
{
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
fin>>n>>m;
nrc=n;
for (;m;m--)
{
int i, j;
fin>>i>>j;
reuniune (i, j);
}
fout<<nrc;
return 0;
}