164. 可达性统计

题目描述

给定一张 N 个点 M 条边的有向无环图，分别统计从每个点出发能够到达的点的数量

基本分析

1. 怎么梳理出统计的顺序？拓扑排序
2. 怎么统计？按照拓扑序的逆序记录可达性
3. N在30000规模，怎么维护可达性？利用bitset进行状态压缩

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <bitset>

using namespace std;

const int N = 30010, M = 30010;
int n, m;

int h[N], e[M], ne[M], idx;
int seq[N], d[N];
bitset<N>f[N];

void add(int x, int y)
{
    e[idx] = y;
    ne[idx] = h[x];
    h[x] = idx ++ ;
}

void topsort()
{
    queue<int> q;
    for (int i = 1; i <= n; i ++)
    {
        if (d[i] == 0)
            q.push(i);
    }
    
    int k = 0;
    while (q.size())
    {
        int t = q.front();
        q.pop();
        // 记录下拓扑序, 索引-节点
        seq[k++] = t;
        // 遍历节点t的指向的节点
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (--d[j] == 0)
                q.push(j);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    // 记得初始化h数组
    memset(h, -1, sizeof h);
    
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
        // 记得维护y的入度
        d[y] += 1;
    }
    
    //排序
    topsort();
    
    // 逆序统计节点的链接关系
    for (int i = n-1; i >= 0; i--)
    {
        int t = seq[i];
        f[t][t] = 1;
        for (int j = h[t]; ~j; j = ne[j])
        {
            int k = e[j];
            f[t] |= f[k];
        }
    }
    
    // count统计结果
    for (int i = 1; i <= n; i++)
        printf("%d\n", f[i].count());
        
    return 0;
}

总结

1. 链式向前星存图
2. 拓扑排序
3. bitset进行状态压缩