欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
}