|
|
可以開一個(gè)閉hash表。棧里面存放的只是hash表的下標(biāo)。這樣比較兩個(gè)set是否一樣，就只需要比較他們的下標(biāo)是否一樣。
同時(shí)對每個(gè)set，要保存它的孩子，一樣存放的是hash表的下標(biāo)。
union和intersect操作，如果是按序存放孩子的話，復(fù)雜度可以低至O(N)。 空間復(fù)雜度為O(N^2)。
 #include <stdio.h>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;
#define SIZE 4096
  struct slot  {
 int *arr;
int cnt;
int hash;
 } table[SIZE];
int stack[SIZE], *sp;
int _pool[SIZE*1024], *pool;
int gethash(int *arr, int cnt)
{
unsigned int h = 0x1653;
while (cnt--)
h = (h*31 + *arr++) & 0x7fffffff;
return h;
}
int insert(int *arr, int cnt)
{
int h = gethash(arr, cnt);
int i = h%SIZE;
while (table[i].hash && table[i].hash != h)
i = (i+1)%SIZE;
  if (!table[i].hash) {
memcpy(pool, arr, cnt*sizeof(int));
table[i].hash = h;
table[i].arr = pool;
table[i].cnt = cnt;
pool += cnt;
 }
return i;
}
void set_union(int *a, int ca, int *b, int cb, int *arr, int *cnt)
{
int i, j;
memcpy(arr, a, ca*sizeof(int));
memcpy(arr + ca, b, cb*sizeof(int));
sort(arr, arr + ca + cb);
for (i = j = 0; i < ca + cb; i++) {
if (i && arr[i] == arr[i-1])
continue;
arr[j++] = arr[i];
}
*cnt = j;
}
int do_union(int a, int b)
{
int arr[SIZE], cnt;
set_union(
table[a].arr, table[a].cnt,
table[b].arr, table[b].cnt,
arr, &cnt
);
return insert(arr, cnt);
}
int do_intersect(int a, int b)
{
int arr[SIZE], cnt, i, j;
cnt = 0;
for (i = 0; i < table[a].cnt; i++) {
for (j = 0; j < table[b].cnt; j++)
if (table[b].arr[j] == table[a].arr[i]) {
arr[cnt++] = table[a].arr[i];
break;
}
}
return insert(arr, cnt);
}
int do_add(int a, int b)
{
int arr[SIZE], cnt;
set_union(table[b].arr, table[b].cnt, &a, 1, arr, &cnt);
return insert(arr, cnt);
}
int main()
{
char op[128];
int t, i, n;
scanf("%d", &t);
while (t--) {
pool = _pool;
sp = stack-1;
for (i = 0; i < SIZE; i++)
table[i].hash = 0;
scanf("%d", &n);
while (n--) {
scanf("%s", op);
if (!strcmp(op, "PUSH")) {
*++sp = insert(NULL, 0);
} else if (!strcmp(op, "DUP")) {
sp[1] = *sp;
sp++;
} else if (!strcmp(op, "UNION")) {
sp[-1] = do_union(sp[0], sp[-1]);
sp--;
} else if (!strcmp(op, "INTERSECT")) {
sp[-1] = do_intersect(sp[0], sp[-1]);
sp--;
} else if (!strcmp(op, "ADD")) {
sp[-1] = do_add(sp[0], sp[-1]);
sp--;
}
printf("%d\n", table[*sp].cnt);
}
printf("***\n");
}
return 0;
}
|