题解 P2712 【摄像头】

Shikita

2018-10-30 13:56:09

Solution

一看就是一道拓扑排序的题目嘛 但是由于我根本不会拓扑排序,所以就用了一个自创的神奇代码 代码 ``` #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; } ``` 就这样吧,姑且应该很好懂吧