読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 0119 : Taro's Obsession

AOJ

問題リンク: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;
}