洛谷月赛 小C与桌游————拓扑排序+贪心+优先队列优化

题解：本题主要考查拓扑排序+贪心+优先队列优化。
简要题意：$n$n个点，$m$m条边的有向无环图,求拓扑序的前缀最大值最多和最少。
1.拓扑排序+贪心：我们发现这道题和拓扑排序有关，知道了这一点，问题就解决了大半。对于求最大的，我们可以贪心的取编号最小的入度相同的点。但对于求最小的，就不能直接贪心取取编号最大的入度相同的点，大部分人（包括我）都是这样错的！因为这样忽略了较小的点！
所以我们讨论一下：如果当前能取的最小值不是前缀最大值，则需要先选他；
否则就选能选的最大值。
2.优先队列优化：上述的我们都要用优先队列维护
代码如下：

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
priority_queue<int,vector<int>,greater<int> >q1;
priority_queue<int,vector<int>,less<int> >q2;
queue <int> q3;
vector<int>g[666666];
int in[663333],in2[663333];
int n,m,ans,maxn=-23333;
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		in[y]++;in2[y]++;
	}
	for(int i=1;i<=n;i++)
	if(in[i]==0){q1.push(i);q2.push(i);}
	while(!q1.empty())
	{
		int t=q1.top();q1.pop();
		if(t>maxn){ans++;maxn=t;}
		for(int i=0;i<g[t].size();i++)
		{
			int k=g[t][i];
			in[k]--;
			if(!in[k]){q1.push(k);}
		}
	}
	cout<<ans<<endl;
	
	ans=0;maxn=-23333;
    while(!q2.empty())
    {
        int t=q2.top();
        if(t>maxn)ans++;
        while(!q2.empty())
		{
            q3.push(q2.top());
            q2.pop();
        }
        while(!q3.empty())
		{
            int tt=q3.front();
            q3.pop();
            maxn=max(maxn,tt);
            for(int j=0;j<g[tt].size();j++)
			{
                int k=g[tt][j];
                in2[k]--;
                if(in2[k]==0)
				{
                    if(k>maxn)q2.push(k);
					else q3.push(k);
                }
            }
        }
    }
	cout<<ans<<endl;
	return 0;
}