Pagini recente » Cod sursa (job #569645) | Cod sursa (job #542085) | Cod sursa (job #932352) | Cod sursa (job #602314) | Cod sursa (job #372579)
Cod sursa(job #372579)
#include <cstdio>
#include <vector>
using namespace std;
#define DIM 50005
#define pb push_back
int t[2 * DIM], nrc, h[2 * DIM];
int radacina(int x)
{
int y =x, tmp;
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 ry = radacina(y),
rx = radacina(x);
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];
}
}
/*
struct nod
{
int x;
nod *next;
};
nod *list[DIM];
int n, m, t, v[DIM], ord[DIM];
void DFS(int q)
{
v[q] = 1;
nod *tt = list[q];
while (tt != NULL)
{
if (!v[tt -> x])
DFS(tt->x);
tt = tt -> next;
}
t++;
ord[t] = q;
}
*/
int main()
{/*
FILE *f = fopen("sortaret.in", "r");
fscanf(f, "%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
list[i] = NULL;
int x, y;
for (int i = 1; i <= m; ++i)
{
nod *t;
fscanf(f, "%d%d", &x, &y);
t = new nod;
t -> x = y;
t -> next = list[x];
list[x] = t;
}
for (int i = 1; i <= n; ++i)
if (!v[i])
DFS(i);
fclose(f);
f = fopen ("sortaret.out", "w");
for (;t;--t)
fprintf (f, "%d ", ord[t]);
for (int i = 1; i <= n; ++i)
{
nod *t = list[i];
while (t != NULL)
printf ("%d ", t->x), t = t -> next;
printf ("\n");
}
fclose(f);
*/
FILE *f = fopen("dfs.in", "r");
int n, m, x, y;
fscanf(f, "%d%d", &n, &m);
nrc = n;
for (;m;--m)
{
fscanf(f, "%d%d", &x, &y);
reuniune(x, y);
}
fclose(f);
f = fopen("dfs.out", "w");
fprintf(f, "%d\n", nrc);
fclose(f);
return 0;
}