Species Tree implements instance code with HashTable

Species Tree is implemented using HashTable

Subject reappear

Title content:

 For a given 1 Species evolution map, 
 The relationship is expressed as follows: 
x y :  said x for y The ancestors. 
1 There's only one species 1 The patriarch, 
1 Our ancestors could have had many different species that evolved, 
 Please find out the grandparent of each species you ask ( The ancestor of ancestors ) . 
 Every species USES it 1 I'm going to use a number that doesn't repeat, 
 If the species does not have a grandparent or does not exist, 
 So take his grandfather's species for granted 0 . ( Born out of thin air )
 Between all species 1 Must have something to do with it, 
 And there's no repeat evolution, 
 The evolution diagram is only going to be 1 Tree. 

 Input format :
 only 1 Set of logging data. 
 The first 1 The guild has two Numbers N , Q , for total N A species and Q A problem. 
 The following N-1 Each line, 1 The row has two Numbers x , y . 
 The meaning is described in the title. 
 The following Q Each line, 1 Row has 1 A digital Z . 
 Represents the species number to be queried. 
 Range of measured assets: 
1 < N < 10000
0 < Q < 1000
0 < x, y, z < 1000000

 Output format: 
 For each 1 Add up the species Numbers of their grandfathers and output them. 

 Input sample: 
6 3
1000 2000
1000 3000
2000 4000
3000 5000
5000 6000
5000
6000
1234

 Output sample: 
4000

 Time limit: 100ms Memory limit: 16000kb

Algorithm implementation

1. Simple array index lookup method

Through the topic request, here you can use the most simple way, because of input x y, y determined value is the same, so here you can define the scope of a y as the size of the array, the subscript is y values, the value of the content is x so convenient for up to 10 points, time complexity is O (1), but will be more waste space.

#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;
}

2. Hash table implementation

Because of the waste of space in method 1, the Hash table is used.

#include <stdio.h>
#include <stdlib.h>
#define NULLKEY -1

typedef struct {
  int *elem; // The element  
  int *elemP; // The parent element  
  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;
}

3. Use C++ map

If you look at the implementation of C, relatively speaking, you should write all the functions by yourself. Here, you can use C++ STL to implement the above problem. It is very simple (I have to say that STL is really easy to use, but it is not as fast as HashTable, and its space is not as small as HashTable's).

#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;
}

Thank you for reading, I hope to help you, thank you for your support of this site!