CH2101可达性问题

拓扑排序应用基础

题意描述

具体见书P95。

给定一个N个点，M条边的有向无环图，问每个点直接或间接可到达的点的数量。

算法分析

书中有详细介绍，这里就不再赘述了。

简而言之就是拓扑排序+状态压缩 。

代码实现

#include
#include
#include
#include
#include
#include
#include
#include
#define N 30030
#define M 30030
using namespace std;

int n,m,f[N],side[N];
int head[N],cnt=0;
struct node{
int to,next;
}edge[M];

vectorpath;
bitsetb[N];
queueq;

void addedge(int x,int y){
    cnt++;
    edge[cnt].next=head[x];
    edge[cnt].to=y;、
    head[x]=cnt;
    return;
}

void topo(){
    for(int i=1;i<=n;i++){
        if(!side[i]) q.push(i)
    }
    while(!q.empty()){
        int now=q.front();
        q.pop();
        path.push_back(now);
        for(int i=head[now];i;i=edge[i].next){
            int y=edge[i].to;
            if(!--side[y]) q.push(y);
        }
    }
    return;
}

int main(){
    memset(side,0,sizeof(side));
    scanf("%d %d",&n,&m);
    int u,v;
    for(int i=1;i<=m;i++){
        scanf("%d %d",&u,&v);
        addedge(u,v);
        side[v]++;
    }
    topo();
    for(int i=path.size()-1;i>=0;i--){
        int u=path[i];
        b[u][u]=1;
        for(int j=head[u];j;j=edge[j].next){
            int v=edge[j].to;
            b[u]|=b[v];
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d\n",b[i].count());
    }
    return 0;
}

结语

（逃…