优先队列思路为何不行
查看原帖
优先队列思路为何不行
1037870
jianxing04楼主2024/1/26 18:35
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
priority_queue<int,vector<int>,greater<int> > q[100009];
int ru[100009],chu[100009];
int main()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		cin>>a>>b;
		q[a].push(b);
        ru[b]++;
        chu[a]++;
	}
    int flag=1;
    int cnt1=0,cnt2=0;
    int Start=1;
    for (int i=1;i<=n;i++)
    {
        if (chu[i]!=ru[i])
        {
            flag=0;
            if (abs(chu[i]-ru[i])>1)
            {
                cout<<"No";
                return 0;
            }
            else if (chu[i]-ru[i]==1)
            {
                Start=i;
                cnt1++;
            }
            else if (ru[i]-chu[i]==1)
            {
                cnt2++;
            }
        }
    }
    if (!((flag==0&&cnt1==1&&cnt2==1)||flag))
    {
        cout<<"No";
        return 0;
    }
    int nex;
    cout<<Start<<' ';
    while(m--)
    {
        nex=q[Start].top();
        q[Start].pop();
        cout<<nex<<' ';
        Start=nex;
    }
    system("pause");
	return 0;
}
2024/1/26 18:35
加载中...