CF915D拓扑求调
  • 板块学术版
  • 楼主best_lover
  • 当前回复19
  • 已保存回复19
  • 发布时间2024/8/19 14:09
  • 上次更新2024/8/19 16:00:38
查看原帖
CF915D拓扑求调
359485
best_lover楼主2024/8/19 14:09

洛谷
Vjudge
CF

#include <bits/stdc++.h>
#define LL long long

using namespace std;

int n, m, in[505];
int meow[505];
vector<int> v[505];

bool topo(){
  queue<int> q;
  int cnt = 0;
  for(int i = 1; i <= n; i++) {
    if(!in[i]) {
      q.push(i);
    }
  }
  while(!q.empty()){
    int s = q.front();
    q.pop();
    cnt++;
    for(auto i : v[s]){
      in[i]--;
      if(in[i] == 0) {
        q.push(i);
      }
    }
  }
  return cnt == n;
}

int main() {

  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> n >> m;
  for(int i = 1, fr, to; i <= m; i++) {
    cin >> fr >> to;
    v[fr].push_back(to);
    in[to]++;
  }

  for(int i = 1; i <= n; i++) {
    meow[i] = in[i];
  }

  for(int i = 1; i <= n; i++) {
    if(in[i]) in[i]--; 
    if(topo()) {
      cout << "YES";
      return 0;
    }
    for(int j = 1; j <= n; j++) {
      in[i] = meow[i];
    }
  }
  
  cout << "NO";
  
  return 0;
}

WA on #14,

脑新的萌子已经被玩坏了球球大佬们帮帮忙叭QAQ

2024/8/19 14:09
加载中...