链接:

https://www.acwing.com/problem/content/166/

题意:

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

思路:

先拓扑排序求出顺序, 再通过bitset利用位运算,记录并集, 可以解决重复计算的问题.

代码:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e4+10;

vector<int> G[MAXN];

vector<int> Tup;

bitset<30010> F[MAXN];

int Dis[MAXN];

int n, m;

void Tupo()

{

    queue<int> que;

    for (int i = 1;i <= n;i++)

    {

        if (Dis[i] == 0)

            que.push(i);

    }

    while (!que.empty())

    {

        int node = que.front();

        que.pop();

        Tup.push_back(node);

        for (int i = 0;i < G[node].size();i++)

        {

            int to = G[node][i];

            if (--Dis[to] == 0)

                que.push(to);

        }

    }

}

void Solve()

{

    for (int i = n-1;i >= 0;i--)

    {

        int x = Tup[i];

        F[x].reset();

        F[x][x] = 1;

        for (int k = 0;k < G[x].size();k++)

        {

            F[x] |= F[G[x][k]];

        }

    }

}

int main()

{

    scanf("%d%d", &n, &m);

    int u, v;

    for (int i = 1;i <= m;i++)

    {

        scanf("%d%d", &u, &v);

        G[u].push_back(v);

        Dis[v]++;

    }

    Tupo();

    Solve();

    for (int i = 1;i <= n;i++)

        printf("%d\n", (int)F[i].count());

    return 0;

}

巴特西

Acwing-164-可达性统计(拓扑排序, 位运算统计)

链接:

题意:

思路:

代码:

最新文章

热门文章