P2712. 摄像头

发表于 分类于 阅读次数： Waline： 本文字数： 329 阅读时长 ≈ 1 分钟

考点

  • 拓扑排序

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e3 + 50;
// arr记录摄像头的位置，is判断当前位置是不是摄像头所在
int n, tot, cnt, head[LEN], ind[LEN], arr[LEN];
bool is[LEN];
queue<int> q;

struct edge {
  int nxt_, to_;
} e[LEN * LEN];

void add(int u, int v) {
  e[tot].nxt_ = head[u], e[tot].to_ = v;
  head[u] = tot++;
}

void toposort() {
  for (int i = 1; i <= n; ++i) {
    if (ind[arr[i]] == 0) {
      q.emplace(arr[i]);
    }
  }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    ++cnt;
    for (int i = head[u]; ~i; i = e[i].nxt_) {
      int v = e[i].to_;
      // 入度为0的摄像头才加入队列，不是摄像头没有意义呀
      if (is[v] && --ind[v] == 0) q.emplace(v);
    }
  }
}

int main() {
  // 链式前向星存储有向边
  memset(head, -1, sizeof(head));
  int u, v, m;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> u;
    is[arr[i] = u] = true;
    cin >> m;
    for (int j = 1; j <= m; ++j) {
      cin >> v;
      ++ind[v];
      add(u, v);
    }
  }
  toposort();
  cnt == n ? cout << "YES" : cout << n - cnt;
}

思路

设有向边A -> B为A监视B

如果拆掉A，被监视的B自然就少一个入度；若要删除B，就必须保证B没有入度（不被监视）

每次都只处理入度为0的结点，其中产生新的入度0结点也要循环处理

显然直接套拓扑排序板子即可....

记得额外新建数组保存摄像头的位置哟~