Pagini recente » Cod sursa (job #142959) | Cod sursa (job #2321104) | Cod sursa (job #2735063) | Cod sursa (job #71438) | Cod sursa (job #372576)
Cod sursa(job #372576)
# include <fstream>
using namespace std;
int n, m, t[100003], nrc, h[100003];
int rad (int x)
{
int y, tmp;
y=x;
while (t[x]) x=t[x];
while (y!=x)
tmp=y, y=t[y], t[tmp]=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;
}