AtCoder Beginner Contest 286(G)

G(欧拉路径)

G

题意大致为\(n\)个点，\(m\)个边的图，然后给出\(k\)条边的编号，问我们这\(k\)条边可不可以在一条路径上（每条边都可以经过）

对于可不可以存在一条路径，里面包含个题目所给的\(k\)条边，其实就是问是否存在一条路可以经历这\(k\)条边，然后我们或许会想到这个有点像欧拉路径

什么是欧拉路径，可以看这儿

这里我们已经知道了判断一个无向图是否是否存在欧拉路径，就是判断奇点的个数（要么是\(0\)要么是\(2\))

但是，我们发现还会有一些没有被选择的边，它可以经过，也可以不经过，我们可以把这些边上的两个点缩成一个点，后面再求在只考虑被选择的边的情况下每一个点的度数，然后根据判断奇点的个数判断是否存在一条欧拉路径包含那\(k\)个边

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
#include <numeric>
using namespace std;
#define int long long 
#define LL long long
#define ios  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const int maxn=2e5+10;
const int mod=998244353;
int n,m,k;
int f[maxn];
bool used[maxn];
int u[maxn],v[maxn];
int d[maxn];
int find(int x)
{
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
void merge(int x,int y)
{
    int tx=find(x),ty=find(y);
    if(tx==ty) return ;
    f[ty]=tx;
    return ;
}
signed main ()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        f[i]=i;
    }
    for (int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i];
    }
    cin>>k;
    for (int i=1;i<=k;i++)
    {
        int x;
        cin>>x;
        used[x]=true;
    }
    for (int i=1;i<=m;i++)
    {
        if(!used[i])
        {
            merge(u[i],v[i]);
        }
    }
    for (int i=1;i<=m;i++)
    {
        if(used[i])
        {
            int x=find(u[i]);
            int y=find(v[i]);
            d[x]++;
            d[y]++;
        }
    }
    int cnt=0;
    for (int i=1;i<=n;i++)
    {
        if(f[i]==i)
        {
            if(d[i]&1) cnt++;
        }
    }
    if(cnt==0||cnt==2)
    {
        cout<<"Yes\n";
    }
    else 
    {
        cout<<"No\n";
    }
    system ("pause");
    return 0;
}

感觉这次\(vp\)的题目有一点水，我竟然石破天惊地写了\(E\),但是\(F\)是交互题，我不会，而且\(G\)补题也很顺利