Acwing_164可达性统计【拓扑排序应用】
程序员文章站
2022-03-14 19:49:08
...
题目链接:Acwing_164可达性统计
AC代码:
#include<iostream>
#include<bitset>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 10, M = 10;
int n, m;
int h[N], e[M], ne[M], idx;
int d[N], q[N];
bitset<N> f[N]; // f[i][k]存储第i个结点对于k结点的可达性,1表示可达,0表示不可达。
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void tuopo()
{
int hh = 0, tt = -1;
for (int i = 1; i <= n; i++)
{
if (!d[i])
{
q[++tt] = i;
}
}
while (hh <= tt)
{
int t = q[hh++];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (--d[j] == 0)
{
q[++tt] = j;
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
fill(h, h + N, -1);
for (int i = 0; i < m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
tuopo();
for (int i = n - 1; i >= 0; i--)
{
int j = q[i];
f[j][j] = 1;//自己可达
for (int k = h[j]; k != -1; k = ne[k]) {
f[j] |= f[e[k]];
}
}
for (int i = 1; i <= n; i++)
{
printf("%d\n", f[i].count());
cout << "---->" << f[i] << endl;
}
system("pause");
return 0;
}