AcWing 164. 可达性统计(搜索)

图的遍历

原题链接

本题思路

1. 建立一个图的邻接表
2. 每个链表里都储存了与之直连的点，那判断一个点的可达性，可求那些直连点自己链表里储存点的并集

优化方案与技巧

• 数组模拟邻接表，节约空间
• 对图进行拓扑排序，即优化搜索顺序
  -- 拓扑排序的特点是越后面的点直连的点越少，即可行方案越少
• bitset 利用bitset存放点，求并集

bitset

将数压缩为二进制形式（内部表现）的十进制（外部表现）

• 需要头文件 #include<bitset>
• 定义bitset时，要明确bitset有多少位：
  -- bitset<32> bit // 32位二进制，初始化为0，0~31
• 常用成员函数
  -- b.count() b中置为1的二进制位的个数
• 详细应用

数组模拟邻接表

int e[N], ne[N], h[N], idx;
void add(int a, int b) {
    e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}

topsort模板

int seq[N];
  void topsort()
{
    queue<int> q;
    //找到没有前件的点即d[] = 0
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q.push(i);
    
    int k = 0;
    while (q.size())
    {
        int t = q.front();
        q.pop();
        seq[k ++ ] = t;
        //一个点出队列则改变直连点的d[]，且往队列加入d[]变成0的
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q.push(j);
        }
    }
}

notes：用c语言的输入输出会快一些

AC代码

#include <cstdio>
#include <iostream>
#include <bitset>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 30005;
int n, m;
int h[maxn], e[maxn], ne[maxn], idx;
int d[maxn], seq[maxn];
bitset<maxn> f[maxn];

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

void topsort()
{
    queue<int> q;
    
    for(int i = 1; i <= n; i++)
        if(!d[i]) q.push(i);
        
    int k = 0;
    while(!q.empty())
    {
        int t = q.front();
        q.pop();
        seq[k++] = 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);
    memset(h, -1, sizeof h);
    
    for(int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a,b);
        d[b]++;
    }
    
    topsort();
    
    for(int i = n-1; i >= 0; i--)
    {
        int j = seq[i];
        f[j][j] = 1;
        for(int k = h[j]; ~k; k = ne[k])
            f[j] |= f[e[k]];
    }
    
    for(int i = 1; i <= n; i++) cout << f[i].count() << endl;
    
    return 0;
}