6.13每日一题题解

E - Ehab and Path-etic MEXs

• 题目链接：https://vjudge.net/contest/377554#problem/E

涉及知识点：

• 思维

solution：

• 其实这个题主要是题意比较难懂
• 下面是我的做法：
• 如果没看懂题意的话，看一下今天我发到群里的图片，或者是自己百度一下题意
• 这个题的解法不止一种，所以我就用了一种我个人认为考虑情况最少的一种
• 首先是记录下每个点的入度
• 然后我们大致可以分为两种点，一种是入度为1，另一种则是入度为大于1
• 然后按照我们输入的边的顺序进行赋值
• 从开始我定义了两个变量，一个是idx = 0,另一个是idx1 = n - 2;
• 首先如果这条边里包括入度为1的点，那么这条边就被设置为idx++
• 如果这个条边里不包含，那么就设置为idx1--
• 这样就能保证为MEX 最大为3

std:

#include <iostream>
#include <unordered_set>
using namespace std;
const int N = 1e6 + 10;
int f[N];
pair<int,int>p[N];
int idx = 0;
int ans[N];
int main()
{
    int n;
    cin >> n;
    int idx1 = n - 2;
    for(int i = 0;i < n - 1;i ++)
    {
        int a,b;
        cin >> a >> b;
        p[i] = {a,b};
        f[a]++;
        f[b]++;
    }
    unordered_set<int>st;
    for(int i = 1;i <= n;i ++)
    {
        if(f[i] == 1){
            st.insert(i);
        }
        if(st.size() >= n - 1){
            break;
        }
    }
    for(int i = 0;i < n - 1;i ++)
    {
        int a = p[i].first,b = p[i].second;
        if(st.count(a) || st.count(b)){
            ans[i] = idx++;
        }
        else{
            ans[i] = idx1--;
        }
    }
    for(int i = 0;i < n - 1;i ++)
    {
        cout << ans[i] << endl;
    }
    return 0;
}