Species Tree 利用HashTable实现实例代码

给定一个物种演化图，关系的表示方式如下：x y : 表示x为y的先祖。一个物种只会有一个先祖，一个先祖可以有很多个演化出来的物种，请你找出每个问题询问物种的祖父物种(先祖的先祖)，每个物种会使用一个不重复的编号来表示，如果该物种没有祖父物种的话或是不存在，那么请将他的祖父物种当是0。(凭空而生)保证所有物种间一定有所关连，且不会有重复演化的现象发生，即演化图只会是一棵树。输入格式:只有一组测资。第一行会有两个数字N、Q，代表总共有N个物种及Q个问题。接下来N-1行，每一行有两个数字x、y，意义如题目所述。接下来的Q行，每一行有一个数字Z，代表要询问的物种编号。测资范围：1 < N < 100000 < Q < 10000 < x, y, z < 1000000输出格式：对于每一个询问的物种编号，将他们的祖父物种编号加总后再输出。输入样例：6 31000 20001000 30002000 40003000 50005000 6000500060001234输出样例：4000时间限制：100ms内存限制：16000kb

#include <stdio.h>#include <string.h>int main(){  int arrBucket[1000000];  int N, Q;  int x, y, z;  long long sum = 0;  memset(arrBucket, 0, sizeof(arrBucket));  scanf("%d %d", &N, &Q);  while(N -- > 1){    scanf("%d %d", &x, &y);    arrBucket[y] = x;  }  while(Q --){    scanf("%d", &z);    if(arrBucket[z] != 0){      if(arrBucket[arrBucket[z]] != 0){        sum += arrBucket[arrBucket[z]];      }    }  }  printf("%lld", sum);  return 0;}

#include <stdio.h>#include <stdlib.h>#define NULLKEY -1typedef struct {  int *elem; //元素   int *elemP; //父元素   int count;}HashTable;int Hash(HashTable H, int k){  return k % H.count;}void InitHashTable(HashTable *H){  int i;  H->elem = (int *)malloc(sizeof(int) * H->count);  H->elemP = (int *)malloc(sizeof(int) * H->count);  for(i = 0; i < H->count; i ++){    H->elem[i] = NULLKEY;    H->elemP[i] = NULLKEY;   }}void InsertHash(HashTable *H, int key, int value){  int addr;  addr = Hash(*H, key);  while(H->elem[addr] != NULLKEY){    addr = (addr + 1) % H->count;  }  H->elem[addr] = key;  H->elemP[addr] = value;}int FindHash(HashTable *H, int key, int *addr){  *addr = Hash(*H, key);  while(H->elem[*addr] != key){    *addr = (*addr + 1) % H->count;    if(H->elem[*addr] == NULLKEY || *addr == Hash(*H, key)){      return 0;    }  }  return 1;}int main(){  int N, Q;  int x, y, z, addr;  long long sum = 0;  HashTable H;  scanf("%d %d", &N, &Q);  H.count = N - 1;  InitHashTable(&H);  while(N -- > 1){    scanf("%d %d", &x, &y);    InsertHash(&H, y, x);  }  while(Q --){    scanf("%d", &z);    if(FindHash(&H, z, &addr)){      if(FindHash(&H, H.elemP[addr], &addr)){        sum += H.elemP[addr];      }    }  }  printf("%lld", sum);  return 0;}

#include <iostream>#include <map>using namespace std;int main() {  int n, q;  cin >> n >> q;  map<int,int> mp;   map<int,int>::iterator it;  int x, y, z;  for (int i=1; i<n; ++i) {      cin >> x >> y;    mp.insert(pair<int,int>(y,x));    }  int sum = 0;  for (int i=0; i<q; ++i) {    cin >> z;    it = mp.find(z);      if (it != mp.end()) {      it = mp.find(it->second);        if (it != mp.end())        sum += it->second;      }  }  cout << sum;  return 0;}