拓扑排序题目求助

常规
1

题目

洛谷P10480

题面

image

image

蒟蒻不会拓扑和bitset，求助

代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> degr, ordr;
vector<bitset<30005>> cnct;
vector<vector<int>> edg;
void bfs()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (degr[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        ordr.push_back(t);
        for (auto targ : edg[t])
        {
            if ((--degr[targ]) == 0)
                q.push(targ);
        }
    }
}
int main()
{
    cin.tie(&cout)->sync_with_stdio(0);
    cin >> n >> m;
    edg.resize(n + 1);
    degr.resize(n + 1);
    cnct.resize(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        edg[u].push_back(v);
        degr[v]++;
    }
    bfs();
    for (int i = 1; i <= n; i++)
        cout << cnct[i].count() << '\n';
    return 0;
}
2

一群好人观猴（红温
image

3

我就是其中一个（

4

求出了拓扑序列如何求可到达的点数？

5

现在WA了,

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> degr, ordr;
vector<bitset<30050>> cnct;
vector<vector<int>> edg, r_edg;
void bfs()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (degr[i] == 0)
            q.push(i);
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        ordr.push_back(t);
        for (auto targ : edg[t])
        {
            if ((--degr[targ]) == 0)
                q.push(targ);
        }
    }
}
int main()
{
    cin.tie(&cout)->sync_with_stdio(0);
    cin >> n >> m;
    edg.resize(n + 1);
    r_edg.resize(n + 1);
    degr.resize(n + 1);
    cnct.resize(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        edg[u].push_back(v);
        r_edg[v].push_back(u);
        degr[v]++;
    }
    bfs();
    for (int i = n; i >= 1; i--)
    {
        cnct[i][i] = 1;
        for (auto targ : r_edg[i])
            cnct[targ] |= cnct[i];
    }
    for (int i = 1; i <= n; i++)
        cout << cnct[i].count() << '\n';
    return 0;
}
6

@杨北辰 我是蒟蒻语法题都不会，我走了 qwq

7

蒟蒻AC了，

8

结帖

拓扑和bitset的用法

拓扑排序:

(bfs)按入度*排序*,取入度为0的结点加入队列，每次取出一个结点，*删除*此结点

*排序*:优先加入入度为0的
*删除*此结点指向的所有结点入度-1

bitset:

摘录：

std::bitset 是标准库中的一个存储 0/1 的大小不可变容器。严格来讲，它并不属于 STL。

由于内存地址是按字节即 byte 寻址，而非比特 bit ，一个 bool 类型的变量，虽然只能表示 0/1 , 但是也占了 1 byte 的内存。
bitset 就是通过固定的优化，使得一个字节的八个比特能分别储存 8 位的 0/1 。

对于一个 4 字节的 int 变量，在只存 0/1 的意义下，bitset占用空间只是其 \frac{1}{32}，计算一些信息时，所需时间也是其 \frac 1{32}。

另外，vector 的一个特化 vector<bool> 的储存方式同 bitset 一样，区别在于其支持动态开空间，bitset 则和我们一般的静态数组一样，是在编译时就开好了的。然而，bitset 有一些好用的库函数，不仅方便，而且有时可以实现 SIMD 进而减小常数。

运算符

  • operator []: 访问其特定的一位。
  • operator ==/operator !=: 比较两个 bitset 内容是否完全一样。
  • operator &/operator &=/operator |/operator |=/operator ^/operator ^=/operator ~: 进行按位与/或/异或/取反操作。

成员函数

  • count(): 返回 true 的数量。
  • size(): 返回 bitset 的大小。
  • test(pos): 它和 vector 中的 at() 的作用是一样的，和 [] 运算符的区别就是越界检查。
  • any(): 若存在某一位是 true 则返回 true，否则返回 false。
  • none(): 若所有位都是 false 则返回 true，否则返回 false。
  • all(): 若所有位都是 true 则返回 true，否则返回 false。

另参: 参见 std::bitset - cppreference.com。

应用