题解 P2712 【摄像头】
Shikita
2018-10-30 13:56:09
一看就是一道拓扑排序的题目嘛
但是由于我根本不会拓扑排序,所以就用了一个自创的神奇代码
代码
```
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0;
char c=getchar();
bool flag=0;
while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();}
while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();}
return flag?-x:x;
}
vector<int>a[505];
queue<int>q;
int n,ans=0;
int b[505],cnt[505];
bool vis[505];
//虽然我想开105来着,但是开了105会RE,我也不知道为什么
int main()
{
n=read();
for(int i=1;i<=n;++i)
{
int x=read(),y=read();
b[i]=x;//离散化?
for(int j=1;j<=y;++j)
{
int z=read();
a[x].push_back(z);//存边
cnt[z]++;//记录有几个连到该点的边(入度)
}
}
for(int i=1;i<=n;++i) if(cnt[i]==0) q.push(i);//初始化
if(q.empty()) {cout<<n<<endl;return 0;}//特判
while(!q.empty())
{
int x=q.front();q.pop();vis[x]=1;
//记录,防止多次处理
int len=a[x].size();//减小查询长度的时间
for(int i=0;i<len;++i)
{
int y=a[x][i];
if(vis[y]) continue;
cnt[y]--;//把所有连边都-1
if(cnt[y]==0) q.push(y);//继续下一个点
}
}
for(int i=1;i<=n;++i) if(cnt[b[i]]==0) ans++;
if(ans==n) cout<<"YES";
else cout<<n-ans;
}
```
就这样吧,姑且应该很好懂吧