【算法每日一练]-图论（保姆级教程 篇2（topo排序，并查集，逆元））#topo排序 #最大食物链 #游走 #村村通

今天讲topo排序

目录

题目：topo排序

思路：

题目：最大食物链

解法一：

解法二： 记忆化

题目：村村通

思路：

---

         

前言：topo排序专门处理DAG（有向无环图）

题目： topo排序

：你有n本书(1~n)，阅读第i本数前你要先读Ci本书，现在你要阅读第一本书，问需要阅读那些书？(答案不唯一)

       

思路：

     

看到这样想遍历下一个节点就需要把所有前置都先遍历过的特点，topo就行了。

先把没有前置的书看一下，然后把后置书的前置书数减一，然后看下一个能看的书。

      

主要就是标记维护一个in数组（存入每个点的前置书数）

      

#include 
using namespace std;
const int N=2e5+5;
vector<int>ve[N];
vector<int>ans;
int n,in[N],vis[N];
void dfs(){//dfs把阅读1书的所有前置书都遍历标记出来，标记出一种方案即可(因为topo序不唯一)
	queue<int>q;
	q.push(1);
	while(!q.empty()){
		int cur=q.front();q.pop();
		for(int i=0,sz=ve[cur].size();i
			int u=ve[cur][i];
			if(!vis[u])q.push(u);vis[u]=1;
		}
	}
}
void topo(){//正序topo排序
	queue<int>q2;
	for(int i=1;i<=n;i++){//先找出入度为0的点。    当然你完全可以写q.push(1)，而我们这里只是为了提供一个topo模板
		if(in[i]==0)q2.push(i),ans.push_back(i);
	}
	while(!q2.empty()){
		int cur=q2.front();q2.pop();
		for(int i=0,sz=ve[cur].size();i
			int u=ve[cur][i];in[u]--;//去掉一个点就减掉相邻点的入度
			if(in[u]==0)q2.push(u),ans.push_back(u);//入队的点都是等待去掉的点
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){//输入每本书需要的前置书Ci
		int cnt,u;cin>>cnt;
		for(int j=1;j<=cnt;j++){
			cin>>u;//每本前置书编号
			ve[i].push_back(u);in[u]++;
		}
	}
	dfs();//标记1的前置书
	topo();//topo排序遍历出需要的书，我们倒序输出即可
	for(int i=ans.size()-1;i>=0;i--){
		if(vis[ans[i]]) cout<' ';
	}
}

           

            

题目：最大食物链

         

解法一：

      

我们标记f[i]是被f[x]捕食的点对应的类食物链数

不难得出： f[x]=∑(f[i])   
首先从生产者开始，每去掉一个被捕食的点，那么相邻捕食者就要加上去掉点的类食物链数，但是我们还需要找到出度为0的消费者。
所以这道题，我们要同时记录入度，还有出度（其实单纯的topo排序就用不上出度，记录出度是为了找食物链结尾的个数）

      

#include 
using namespace std;
const int MOD=80112002,M=500005,N=5005;
vector <int>v[N];
queue<int> q;
int n,m,ans,f[N],in[N],out[N];//我们需要标记每个点的入度和出度，f为以该点结尾的类食物链数
int main(){
	cin>>n>>m;int x,y;
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		v[x].push_back(y);//y吃x，x指向y
		out[x]++;in[y]++;
	}
	for(int i=1;i<=n;i++){//找到所有没有入度的点为起点
		if(in[i]==0){q.push(i);f[i]=1;}
	}
	while(q.size()){//进行拓扑排序
		int cur=q.front();q.pop();
		for(int i=0,sz=v[cur].size();i
			int t=v[cur][i];
			f[t]=(f[t]+f[cur])%MOD;in[t]--;//去掉cur点的话，就要把f[cur]加到捕食它的点上
			if(in[t]==0) q.push(t);
		}		
	}
	for(int i=1;i<=n;i++){
		if(out[i]==0)ans=(ans+f[i])%MOD;//出度为0的点的f是我们要的真正食物链数
	}
	cout<
	return 0;
}

           

解法二： 记忆化

 
#include     //记忆化搜索
using namespace std;
const int N=1e5+5;
int n,m,ans,tot,in[N],out[N],f[N];
vector<int>ve[N];
int dfs(int x){//就是从每个生产者开始，看看能到多少个最终消费者，然后记忆化，最终计算所有生产者就是答案
	if(f[x])return f[x];
	if(!out[x])return 1;
	for(int i=0,sz=ve[x].size();i
		int v=ve[x][i];
		f[x]+=dfs(v);
	}
	return f[x];
}
int main(){
	cin>>n>>m;int u,v,w;
	while(m--){
		cin>>u>>v;
		ve[u].push_back(v);
		out[u]++;in[v]++;
	}
	for(int i=1;i<=n;i++){
		if(in[i]==0&&out[i])
		ans+=dfs(i);
	}
	cout<
}

         

        

题目：游走

         

思路： 

       

给一个DAG(有向无环图)，求所走路径长度的期望呗！也就是：所有路径长度总和/所有路径个数（因为每条路径概率都一样嘛）

        

明明是DAG图，topo一下完事了

我们设置g[i]表示以i为终点的路径数，f[i]表示i为终点的长度和

   
topo：从点j到一个点i，则g[i]+=g[j],f[i]+=f[j]+g[i]（因为啊，从j到i的每个路径长度都只增加1就行，一共增加了g[i]）

        
最后就是求(L/S)MOD，也就是L*(S^(MOD-2))MOD即可（逆元小知识）

        

#include 
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
const ll MOD=998244353;
int n,m;
ll L,S,f[MAXN],g[MAXN];//g[i]表示以i为终点的路径数，f[i]表示i为终点的长度和
vector<int> edge[MAXN];
int in[MAXN],vis[MAXN];
void topo(void)//模板
{
	queue<int> q;
	for(int i=1;i<=n;i++)
    if(!in[i]) q.push(i);
    while(!q.empty())
    {
    	const int u=q.front();
    	q.pop();
    	if(vis[u]) continue; vis[u]=true;//没有环，所以这句话可以不要
    	for(auto v:edge[u])
    	{
    		in[v]--;
    		if(!in[v])	q.push(v);
    		f[v]=(f[v]+f[u]+g[u])%MOD;
    		g[v]=(g[v]+g[u])%MOD;
		}
	}
}
 
ll qpow(ll base,ll k)//快速幂求逆元
{
	ll res=1;
	while(k)
	{
		if(k&1)	res=res*base%MOD;
		base=base*base%MOD;
		k>>=1;
	}
	return res;
}
 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;cin>>u>>v;
		edge[u].push_back(v);
		in[v]++;
	}
	for(int i=1;i<=n;i++)	g[i]=1;//初始化:每个点的路径数初始化为1
	topo();
	for(int i=1;i<=n;i++)	L=(L+f[i])%MOD;//获取最终的总长度
	for(int i=1;i<=n;i++)	S=(S+g[i])%MOD;//获取最终的路径个数
	cout<<(L*qpow(S,MOD-2))%MOD<//求L/S的结果，即L*S的逆元，即L*S^(MOD-2)
	return 0;
}

提一嘴： 

                    
为什么要引入逆元呢？
因为(a+b)%MOD=(a%MOD+b%MOD)%MOD
(a-b)%MOD=(a%MOD-b%MOD)%MOD
(a*b)%MOD=(a%MOD*b%MOD)%MOD  

            
但是除法不满足，我们要求(a/b)%p=1等价于(a*x)%p=1，这个x就是b的乘法逆元（可以理解成x为1/b），也就是(b*x)%p=1

        
再引入费马小定理：假如a和p互质，那么a^(p-1)=1(%p)，故a*a^(p-2)=1(%p)，故a的逆元x=a^(p-2)%p
因此：(x/y)%p等价于x*y^(p-2)%p，注意每乘一次就要去一次模
     

        

                 

题目：村村通

 

            

思路：

       

并查集步骤：
1，初始化每个点的父亲为自身
2，查找每两个元素所在的集合，找到两个祖宗后返回任意一个并路径压缩（修改中间点的父亲编号为祖宗编号）
3，最后查找有几个祖宗即可（因为有相同的祖宗，就说明祖宗可以到的所有点，也就是它们都是互通的）
      

#include                
using namespace std;
int fa[1000001], n, m, x, y;
int find(int x)//找到祖先，并将中间的点的父亲都修改成祖宗编号（路径压缩） 
{
    if(x!=fa[x])//当x不等于它的爸爸时(还有祖先) 
    	fa[x]=find(fa[x]);//找到祖先，并修改父亲
    return fa[x];//返回祖先 
}
void unity(int x, int y)
{
    int f1=find(x);//找到x的祖先 f1
    int f2=find(y);//找到y的祖先 f2
    fa[f1]=f2;//祖先和祖先结为父子(谁是父亲谁是儿子都可以) 
}
int main()
{
	while(true)
	{
		int ans=0;
		cin>>n>>m;
		if(n==0) return 0;
	    for(int i=1; i<=n; i++){
	    	fa[i]=i;//初始化自己的父亲是自己 
		}
	    for(int i=1; i<=m; i++){
	    	scanf("%d %d", &x, &y);//一点点把图连通起来
	        unity(x,y);//连通：合并x和y各自能到的地方
		}
	    for(int i=1; i<=n; i++){//自己的父亲等于自己本身
	    	if(find(i)==i) ans++;
		}
		printf("%d\n", ans-1);//共需修ans-1条路即可
	}
    return 0;
}