henrytb 的博客

henrytb 的博客

题解 P2712 【摄像头】

posted on 2018-07-23 20:08:03 | under 题解 |

裸的拓扑排序

先输入图,本题因为数据较小,直接使用邻接矩阵存储。并且记录每个点入度。

然后依次删掉入度为0的点,每删一个更新与这个点相邻的点的入度。然后再删掉入度为0的点,一直重复,直到没有入度为0的点或删完为止。

PS:此题有坑,在于点的编号不连续,用一个used数组存储有没有这个点。

附上code:

#include <bits/stdc++.h>//万能头文件qwq
using namespace std;
const int N=505;
int n,m,x,ma[N][N],k,du[N],q[10*N],l=1,r,maxx;
bool used[N];//记录有没有这个点
int main(){
//-----------读入------------
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&m);
        used[x]=true;
        for(int j=1;j<=m;j++){
            scanf("%d",&k);
            ma[x][k]=1;
            du[k]++;
        }
        maxx=max(maxx,x);//最大的点编号
    }
//-----------拓扑排序------------------
    for(int i=0;i<=maxx;i++)
        if(du[i]==0&&used[i])q[++r]=i;//将入度为0的点放入队列
    int ans=0;//记录删了多少个点
    while(ans<n){
        if(l>r){//不可再删
            printf("%d",n-ans);
            return 0;
        }
        int cmd=q[l++];//删点
        for(int i=0;i<=maxx;i++){
            if(ma[cmd][i]&&used[i]){
                du[i]--;//处理与被删的点相邻的点的入度
                if(du[i]==0&&used[i])q[++r]=i;//如果此点更新后入度为0,将此点放入队列
            }
        }
        ans++;//更新已删的点的个数
    }
    if(ans==n)printf("YES");
    return 0;
}