結果

問題 No.679 不思議マーケット
ユーザー tetsu
提出日時 2018-04-27 23:55:59
言語 C++14
(gcc 8.3.0)
結果
AC  
実行時間 9 ms
コード長 1,312 Byte
コンパイル時間 1,288 ms
使用メモリ 8,920 KB
最終ジャッジ日時 2019-10-19 21:37:33

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
input00.txt AC 4 ms
6,872 KB
input01.txt AC 3 ms
6,872 KB
input02.txt AC 4 ms
6,876 KB
input03.txt AC 9 ms
6,876 KB
input04.txt AC 5 ms
6,876 KB
input05.txt AC 6 ms
6,876 KB
input06.txt AC 5 ms
6,876 KB
input07.txt AC 5 ms
6,876 KB
input08.txt AC 6 ms
6,876 KB
input09.txt AC 4 ms
6,876 KB
input10.txt AC 4 ms
6,872 KB
input11.txt AC 5 ms
6,872 KB
input12.txt AC 4 ms
6,876 KB
input13.txt AC 5 ms
6,872 KB
input14.txt AC 5 ms
6,876 KB
input15.txt AC 4 ms
8,920 KB
input16.txt AC 4 ms
6,872 KB
input17.txt AC 3 ms
6,872 KB
テストケース一括ダウンロード

ソースコード

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