結果

問題 No.679 不思議マーケット
ユーザー tetsu
提出日時 2018-04-27 23:55:59
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 1,312 bytes
コンパイル時間 1,601 ms
コンパイル使用メモリ 166,416 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-27 22:32:30
合計ジャッジ時間 2,293 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const int NMAX = 501;

int getNext(int deg[], int n, bool taken[]) {
  //  printf("getNext\n");
  for(int i=1; i<=n; i++) {
    //printf("deg[%d]==%d&&!taken[%d]=%d\n", i, deg[i], i, taken[i]);
    if(deg[i]==0&&!taken[i]) {
      return i;
    }
  }
  return -1;
}

int main() {
  int n, m;
  cin >> n >> m;
  bool dep[NMAX][NMAX];
  for(int i=0; i<NMAX; i++) {
    for(int j=0; j<NMAX; j++) {
      dep[i][j] = false; // i requires j
    }
  }
  int deg[NMAX] = {};
  for(int i=0; i<m; i++) {
    int g, r;
    cin >> g >> r;
    for(int j=0; j<r; j++) {
      int h;
      cin >> h;
      dep[g][h] = true; // h -> g
      deg[g]++;
    }
  }
  // for(int i=1; i<=n; i++) {
  //   // for(int j=1; j<=n; j++) {
  //   //   if(dep[i][j]) {
  //   // 	printf("%d -> %d\n", j, i);
  //   //   }
  //   // }
  //   printf("deg[%d] = %d\n", i, deg[i]);
  // }
  int ans = 0;
  int next = 0;
  bool taken[NMAX] = {};
  for(int i=0; i<NMAX; i++) {
    taken[i] = false;
  }
  //  printf("getNext(deg, n, taken)=%d\n", getNext(deg, n, taken));
  while((next = getNext(deg, n, taken)) != -1) {
    taken[next] = true;
    ans++;
    for(int j=1; j<=n; j++) {
      if(dep[j][next]) {
	dep[j][next] = false;
	deg[j]--;
      }
    }
  }
  cout << ans << endl;
  return 0;
}
0