用multiset怎么求解呀,这个代码只有十分
查看原帖
用multiset怎么求解呀,这个代码只有十分
556824
hhyyd楼主2022/5/6 17:24
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int N = 1e5+10,M = 2e5+10;
multiset<int> g[N];
int p[N],ans[N],top;
int din[N],dout[N];
int n,m;
int check(vector<int> tmp)
{
    if(tmp.size() == 1 || tmp.size() > 2) return 0;
    if(tmp.size() == 2)
    {
        int v1 = tmp[0],v2 = tmp[1];
        if(dout[v1] - din[v1] == 1 && din[v2] - dout[v2] == 1) return v1;
        else if(dout[v2] - din[v2] == 1 && din[v1] - dout[v1] == 1) return v2;
        else return 0;
    }
    else return 1;
}
void dfs(int u)
{
    while(g[u].size())
    {
        int t = *g[u].begin();
        g[u].erase(t);
        dfs(t);
    }
    ans[++top] = u;
    
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ )
    {
        int a,b;
        cin >> a >> b;
        g[a].insert(b);
        din[b]++,dout[a]++;
    }
    vector<int> tmp; // 记录出度不等于入度的点
    for (int i = 1; i <= n; i ++ )
    {
        if(din[i] != dout[i])
        {
            tmp.push_back(i);
        }
    }
    
    int t = check(tmp);
    
    if(!t)
    {
        puts("No");
        return 0;
    }
    dfs(t);
    for (int i = top; i >= 1; i -- )
    {
        cout << ans[i] << " ";
    }
    return 0;
}
2022/5/6 17:24
加载中...