数据结构——拓扑排序经典例题

╰半橙微兮° 2021-12-02 00:18 397阅读 0赞

定义：  
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

步骤：

(1) 选择一个入度为0的顶点并输出；  
(2) 从网中删除此顶点及所有出边。

如果输出的顶点数小于输入的顶点数，说明这不是一个拓扑序列，该图存在环。

代码思想：  
用vector存入边的信息，设置一个入度的数组，存入度的数量，

topsort函数：  
用队列存拓扑序列，先把入度为0的顶点全部入队，取出队列第一个点，输出顶点并把这个顶点的所有出边的入度-1，并判断是不是有新的入度为0的顶点，如果有则入队。直至队列中的所有顶点输出。

例题1：  
[确定比赛名次][Link 1]  
输出一个拓扑序列，并且字典序小的先输出。（此题保证不存在环）

思路：把模板的队列改成优先队列（有小到大）。

#include<iostream>
    #include<cstring>
    #include<queue>
    #include<functional>
    #include<vector>
    using namespace std;
    typedef long long ll;
    const int maxn=510;
    vector<int>vec[maxn];
    int du[maxn];
    int n,m;
    
    void topsort()
    {
    	priority_queue<int,vector<int>,greater<int> > s;
    	int flag=0;
    	while(!s.empty())
    		s.pop();
    	for(int i=1;i<=n;i++)
    	{
    		if(!du[i])
    			s.push(i);
    	}
    	while(!s.empty())
    	{
    		int now=s.top();
    		if(flag==0)
    		{
    			cout<<now;
    			flag=1;
    		}
    		else
    			cout<<" "<<now;
    		s.pop();
    		for(int i=0;i<vec[now].size();i++)
    		{
    			if(--du[vec[now][i]]==0)	
    				s.push(vec[now][i]);
    		}
    	}
    }
    int main()
    {
    	while(cin>>n>>m)
    	{
    		memset(du,0,sizeof(du));
    		for(int i=1;i<=n;i++)
    			vec[i].clear();
    		for(int i=1;i<=m;i++)
    		{
    			int a,b;
    			cin>>a>>b;
    			vec[a].push_back(b);
    			du[b]++;
    		}
    		topsort();
    		cout<<endl;
    	}
    	return 0;	
    }

例题2：只是判断是否存在环

[Legal or Not][]

思路：用拓扑排序就可以判断是否为环。

#include<iostream>
    #include<vector>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int maxn=110;
    int n,m;
    vector<int>vec[maxn];
    queue<int>s;
    int du[maxn];
    bool topsort()
    {
    
    	int num=0;
    	while(!s.empty())	
    		s.pop();
    	for(int i=0;i<n;i++)
    	{
    		if(!du[i])
    			s.push(i);
    	}
    	while(!s.empty())
    	{
    		int ans=s.front();
    		s.pop();
    		num++;
    		for(int i=0;i<vec[ans].size();i++)
    		{
    			if(--du[vec[ans][i]]==0)
    				s.push(vec[ans][i]);
    		}
    	}
    	//cout<<num<<endl;
    	if(num==n)	return true;
    	return false;
    }
    int main()
    {
    	while(cin>>n>>m,n,m)
    	{
    		memset(du,0,sizeof(du));
    		for(int i=0;i<n;i++)
    			vec[i].clear();
    		for(int i=1;i<=m;i++)
    		{
    			int a,b;
    			cin>>a>>b;
    			vec[a].push_back(b);
    			du[b]++;
    		}
    		if(topsort()) cout<<"YES"<<endl;
    		else cout<<"NO"<<endl;
    	}
    	return 0;
     }

例题3：  
[Almost Acyclic Graph][]

给你m条边，不确定有没有环，删除一条边，看是否可以构成有向无环图。

还是判环，我们如果删除每一条边，再进行拓扑排序，时间到了1e7级别，估计会超时。

正解：O（n\*m）得到做法，topsort函数不变，记录每一个顶点入度的次数，我们只需要每一次尝试入度大于等于1的顶点-1，尝试一下拓扑排序，因为入度-1，说明其中的某一条边给删掉了，尝试每一个入度>=1的点就可以得到答案。为啥不尝试入度为0的点，因为入度为0的点这条边构不成环，自己可以想想。

#include<iostream>
    #include<cstring>
    #include<queue>
    #include<vector>
    using namespace std;
    const int maxn=1000;
    typedef long long ll;
    ll rudeg[maxn],indeg[maxn];//ru为标准 in为操作 
    vector<ll> vec[maxn];
    ll n,m;
    int  topsort()
    {
    	queue<ll> q;
    	while(!q.empty()) q.pop();
    	for(int i=1;i<=n;i++)
    	{	
    		if(!indeg[i]) 
    			q.push(i);
    	}
    	ll num=0;
    	while(!q.empty())
    	{
    		ll t=q.front();
    		q.pop();
    		num++;
    		for(int i=0;i<vec[t].size();i++)
    		{
    			if(--indeg[vec[t][i]]==0)
    			{
    				q.push(vec[t][i]);
    			}
    		}
    	}
    	if(num==n)	return 1;
    	return 0;
    }
    int main()
    {
    	while(cin>>n>>m)
    	{
    		for(int i=0;i<=n;i++)
    			vec[i].clear();
    		ll flag=0; 
    		memset(rudeg,0,sizeof(rudeg));
    		memset(indeg,0,sizeof(indeg));
    		for(int i=1;i<=m;i++)
    		{
    			ll a,b;
    			cin>>a>>b;
    			vec[a].push_back(b);
    			indeg[b]++;
    			rudeg[b]++; 
    		}
    		if(topsort())
    		{
    			flag=1;
    		}
    		else
    		{
    			for(int i=1;i<=n;i++)
    			{
    				for(int i=1;i<=n;i++)
    					indeg[i]=rudeg[i];
    				if(indeg[i]>=1)
    				{
    					indeg[i]--;
    					if(topsort())
    					{
    						flag=1;
    						break;
    					}
    				}
    			}
    		}
    		if(flag)
    			cout<<"YES"<<endl;
    		else
    			cout<<"NO"<<endl;
    	}
    	return 0;
     }

例题4：  
[reward][]

也是一个拓扑序列，每个人基础888元，a->b 说明a要比b大1（贪心的思想）。  
也就是b->a a的层数比b大1层 总金额=前一个金额+1；

#include<iostream>
    #include<queue>
    #include<vector>
    #include<cstring>
    using namespace std;
    const int maxn=2e4+10;
    vector<int>vec[maxn];
    queue<int> q;
    int n,m;
    int du[maxn],money[maxn],num,sum;
    
    void topsort()
    {
    	while(!q.empty()) q.pop();
    	
    	for(int i=1;i<=n;i++)
    	{
    		if(!du[i])	
    		{
    			q.push(i);
    			money[i]=888;
    		}
    	}
    	
    	num=0;
    	sum=0;
    	while(!q.empty())
    	{
    		int now=q.front();
    		sum+=money[now];
    		q.pop();
    		num++;
    		for(int i=0;i<vec[now].size();i++)
    		{
    			if(--du[vec[now][i]]==0)	
    			{
    				q.push(vec[now][i]);
    				money[vec[now][i]]=money[now]+1;
    			}
    		 } 
    	}
    	if(num==n)
    		cout<<sum<<endl;
    	else
    		cout<<"-1"<<endl;
    }
    int main()
    {
    	while(cin>>n>>m)
    	{
    		memset(du,0,sizeof(du));
    		memset(money,0,sizeof(money));
    		for(int i=0;i<n;i++)
    		{
    			vec[i].clear();
    		}
    		
    		for(int i=1;i<=m;i++)
    		{
    			int a,b;
    			cin>>a>>b;
    			vec[b].push_back(a);
    			du[a]++;
    		}
    		
    		topsort();
    	}
    	return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1285
[Legal or Not]: http://acm.hdu.edu.cn/showproblem.php?pid=3342
[Almost Acyclic Graph]: https://codeforces.com/problemset/problem/915/D
[reward]: http://acm.hdu.edu.cn/showproblem.php?pid=2647