ACM: 115 - Climbing Trees

這題寫出來也很感動，原因一是自己想到演算法解出了graph題！原因二是寫完以後de了超久的bug，明明自己測試output都正確，一直找不到runtime error的原因。看超久才發現原來是把一個變數放錯資料型別，改了以後總算AC了！

我用一個一維陣列存每個child的parent，再不斷trace。

CODE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NAMES 300
#define LEN_NAME 31

int tree[MAX_NAMES], maxn;
char name[MAX_NAMES][LEN_NAME+1];

int addname(char *s);
int findname(char *s);
void qry(int p, int q);
void showtrace(int t);
int isdescendent(int p, int q, char *s);
int iscousin(int p, int q);

int main(){
  int pk, qk;
  char p[LEN_NAME+1], q[LEN_NAME+1];
  
  maxn = 0;
  while( scanf("%s %s", p, q) == 2 ){
    if( strcmp(p, "no.child") == 0 )
      break;
    else{
      pk = addname(p);
      qk = addname(q);
      tree[pk] = qk;
    }
  }/*while parent-child pairs input*/
  
  /*read query*/
  while( scanf("%s %s", p, q) == 2 ){
    pk = findname(p);
    qk = findname(q);
    qry(pk, qk);
  }/*while query input*/
  
  exit(0);
}

int addname(char *s){
  int i;
  
  /*check if name exists*/
  for(i=0; i<maxn; i++)
    if( strcmp(s, name[i]) == 0 )
      return i;
  
  /*add new name*/
  strcpy(name[maxn], s);
  tree[maxn] = maxn;
  maxn++;
  
  return (maxn-1);
}

int findname(char *s){
  int i;
  
  for(i=0; i<maxn; i++)
    if( strcmp(s, name[i]) == 0 )
      return i;
  
  return -1;
}

void qry(int p, int q){ 
  if( p != -1 && q != -1 ){
    if( tree[p] == tree[q] ){
      printf("sibling\n");
      return;
    }
    if( isdescendent(p, q, "child") == 1 )
      return;
    if( isdescendent(q, p, "parent") == 1 )
      return;
    if( iscousin(p, q) == 1 )
      return;
  }/*if p, q != -1 */
  
  printf("no relation\n");
  return;
}

void showtrace(int t){
  int i;
  
  if( t == 0 )
    return;
  for(i=t; i>1; i--)
    printf("great ");
  printf("grand ");
}

int isdescendent(int p, int q, char *s){
  int tp, trace;
  
  tp = p;
  trace = 0;
  while( tree[tp] != tp ){
    tp = tree[tp];
    if( tp == q ){
      showtrace(trace);
      printf("%s\n", s);
      return 1;
    }
    trace++;
  }
  
  return 0;
}

int iscousin(int p, int q){
  int tp, tq, m, n;
  
  tp = p;
  tq = q;
  m = n = 0;
  while( tp != tree[tp] ){
    tp = tree[tp];
    while( tq != tree[tq] ){
      tq = tree[tq];
      if( tp == tq ){
        if( m > n ){
          printf("%d cousin ", n);
          printf("removed %d\n", (m-n));
        }
        else if( m == n )
          printf("%d cousin\n", m);
        else{
          printf("%d cousin ", m);
          printf("removed %d\n", (n-m));
        }
        return 1;
      }/*if common ancestor found*/
      n++;
    }/*while: trace q*/      
    tq = q;
    n = 0;
    m++;
  }/*while: trace p*/
  
  return 0;
}