拓扑排序一＞可达性统计

拓扑排序

给定一张有向无环图，排出所有顶点的一个序列A满足：
对于途中的每条有向边（x,y),x在A中都出现在y之前，则称A是该图的顶点的一个拓扑序。

拓扑序列可以判断有向图中是否有环，可以生成拓扑序列。

Kahn（卡恩）算法
每个点通过有向边都有几个邻点，e[x]存点x的邻点，用tp存拓扑序列，再开一个数组，是x的入度数组din[x]存点x的入度。
算法的核心用队列维护一个入度为0的节点的集合

• 1.初始化，队列q压入所有入度为0的点。
• 2.每次从q中取出一个点x放入数组tp。
• 3.然后将x的所有出边删除。若将边（x,y)删除后，y的入度变为0，则将y压入q中。
• 4.不断重复2.3过程，直到队列q为空。
• 5.若tp中的元素个数等于n，则有拓扑序，否则，有环。

代码展示：

vector <int>e[N],tp;//e[N]存x的邻点，tp存拓扑序列 
int din[N];//存x的入度，当x的入度为0时就可以添加到拓扑序中了 
bool toposort()
{
	queue<int>q;
	for(int i=1;i<=n;i++)
	if(din(i)==0)q.push(i);//将一开始入度为0的点压入队列 
	while(q.size())//当q不空的时候 
	{//因为q中都是入度为0的点，且是有序的 
		int x=q.front(); //取队首元素 
		q.pop();//记得要弹出 
		tp.push_back(x);//存入tp数组中 
		for(auto c:e[x])//少了一个点，那么从这个点出来的边都要删除 
		{
			if(--din[c]==0)//如果删除后，入度等于0 
			q.push(c);//就压入队列 
		}
	}
	return tp.size()==n;//当所有进行完后，判断拓扑序的长度是否等于n 
}
int main()
{
	cin>>n>>m;//n个点m条边 
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;//(a,b) 
		e[a].push_back(b);//存边 
		din[b]++;//记录入度的个数 
	}
	if(!toposort())//如果拓扑序不等于n，那就有环，没有答案 
	puts("-1");
	else
	{
		for(auto x:tp)//n个的话，输出拓扑序 
		printf("%d ",x);
	}
	return 0;
}
 
 

流程

经典例题

164. 可达性统计

164. 可达性统计

解题思路：

• 先对这个有向无环图进行拓扑排序得到一个拓扑序列。
• 然后通过逆序dp计算可达集合，逆序可以确保处理一个节点时它的后继节点已经被计算过了。
  计算方式：dp[x] |=dp[y] y是x的后继节点
• 用bitset处理，结果直接输出dp[i].count().
  注释非常详细！

AC代码

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
#define PII pair<int,int>
#define fi first
#define se second
#define endl '\n'
const int N=3e5+5;
int n,m,a,b;
vector <int>e[N],tp;//e[N]存x的邻点，tp存拓扑序列 
int din[N];//存x的入度，当x的入度为0时就可以添加到拓扑序中了 
bitset<30005>dp[N]; 
bool toposort()
{
	queue<int>q;
	for(int i=1;i<=n;i++)
	if(din[i]==0)q.push(i);//将一开始入度为0的点压入队列 
	while(q.size())//当q不空的时候 
	{//因为q中都是入度为0的点，且是有序的 
		int x=q.front(); //取队首元素 
		q.pop();//记得要弹出 
		tp.push_back(x);//存入tp数组中 
		for(auto c:e[x])//少了一个点，那么从这个点出来的边都要删除 
		{
			if(--din[c]==0)//如果删除后，入度等于0 
			q.push(c);//就压入队列 
		}
	}
}
signed main()
{
	cin>>n>>m;//n个点m条边 
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;//(a,b) 
		e[a].push_back(b);//存边 
		din[b]++;//记录入度的个数 
	}
	toposort();//拓扑排序 
	for(int i=n-1;i>=0;i--)
	{
		int t=tp[i];
		dp[t][t]=1;//每个节点可达自身，所以赋值为1 
		for(auto c:e[t])//将所有后继节点的可达集合进行“或”操作 
		dp[t]|=dp[c];//c是t的后继 
	}
	for(int i=1;i<=n;i++)
	cout<<dp[i].count()<<endl;//每个节点的bitset值中的1的个数就是可达的数量 
	return 0;
}
 
 

啊好难~