PKU : 2491 - Scavenger Hunt

実装問題

問題概要

http://poj.org/problem?id=2491

あるスタート地点からゴール地点まで, S個の地点を経由して歩きました.
そのときの記録が, S-1個, 順番がバラバラに与えられるので, 正しい順番に並び替えてください.

アルゴリズム

スタート地点は, 簡単に決めることができます.
S-1個の右側に出てこなかった文字列がスタート地点です.
例えば, 以下の例の場合, 右側に出てこない文字列 VideoGameがスタート地点になります.

3
左側       右側
Toilet     Hospital
VideoGame  Toilet

あとは, スタート地点から順番にS個の文字列を辿るだけで解けます.

プログラム

int main(){
  int T;
  char buff[1024];
  scanf("%d",&T);

  for(int SET=1;SET<=T;SET++){
    printf("Scenario #%d:\n",SET);

    int S;
    scanf("%d",&S);

    map<string,string> route;
    map<string,int> cnt;
    for(int i=0;i<S-1;i++){
      string from,to;

      scanf("%s",buff);
      from = string(buff);
      scanf("%s",buff);
      to = string(buff);

      route[from] = to;
      cnt[from] = 0;
      cnt[to]++;
    }

    string now;
    for(map<string,int>::iterator iter=cnt.begin();;iter++){
      if((iter->second) == 0){
        now = (iter->first);
        break;
      }
    }

    puts(now.c_str());
    for(int i=0;i<S-1;i++){
      now = route[now];
      puts(now.c_str());
    }

    printf("\n");
  }
}