AOJ 0119 : Taro's Obsession
問題リンク:Taro's Obsession | Aizu Online Judge
問題概要:
m-1人の人と1匹の猫がいる
m-1人の証言から推測される部屋に入った人or猫の順番をどれか1つ出力せよ
※ただし猫は一番最後部屋にはいったことがわかっている
使用した言語:C++
解法:
部屋に入るところを見られた数をカウントしていく
誰にも見られていない人を出力し、その人がみた人のカウントを1つ減らす という操作を繰り返す
だたし猫(2番)は最後に出力するようにする
普段問題を解く際にnを人とかものの数にするのだが、今回はmとnが自分のイメージと完全に逆でループも間違ってm回まわすところをn回まわしてしまったりして3回間違えてしまった
反省
コード:
#include<iostream> #include<vector> using namespace std; int main() { int n,m; cin >> m >> n; vector<int> per; vector<vector<int> > G; G.resize(m); bool used[m]; per.resize(m); for(int i=0;i<m;i++) per[i] = 0,used[i] = false; for(int i=0;i<n;i++) { int x,y; cin >> x >> y; x--,y--; per[y]++; G[x].push_back(y); } used[1] = true; for(int i=0;i<m;i++) { for(int j=0;j<m;j++) { if(used[j]) continue; if(!per[j]) { used[j] = true; cout << j+1 << endl; for(int k=0;k<G[j].size();k++) per[G[j][k]]--; } } } cout << 2 << endl; return 0; }