摄像头

拓补排序
找入度为零的,就是没被监视的,删掉
继续找入度为零的,继续删
直到找不到
输出答案

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
int n,t;int r[199999],c[1999][1999],a[19999],f,flag[19999];
int main()
{
scanf("%d",&n);

for(int i=1;i<=n;i++)
{
int x;
scanf("%d%d",&a[i],&x);
c[a[i]][0]=x;
//printf("\n%d %d",a[i],c[a[i]][0]);
for(int j=1;j<=c[a[i]][0]; j++)
{
scanf("%d",&x); c[a[i]][j]=x;
r[x]++;
}
}
f=1;

while(f)
{
f=0;
for(int i=1;i<=n;i++)
if(r[a[i]]==0&&!flag[a[i]])
{
++t,f=1;flag[a[i]]=1;
for(int j=1;j<=c[a[i]][0];j++)
r[c[a[i]][j]]--;
}


}
if(t==n)printf("YES");
else printf("%d",n-t);
}
最近的文章

day5

exam简单的贪心注意细节,long long就可以ac了123456789101112131415161718192021222324252627282930313233343536373839#include&lt;cstdio&gt;#include&lt;iostream&gt;#inclu …

于  2017 继续阅读
更早的文章

搜索

华容道70设两个变量,记在一个结构体里在进行爆搜,就是一个普通的bfs,只会简单的爆搜,正解是,三个bfs,先处理出白板到起始的最短距离,在处理出移动的代价,在跑一边最短路;123456789101112131415161718192021222324252627282930313233343536 …

于  bfsdfs 继续阅读