UCF “Practice” Local Contest — Aug 25, 2018 I. Aqua loves painting 一笔画 画几笔 （欧拉路 + （带权）并查集）

Problem Aqua loves painting 
Input file:     standard input  Output file:    standard output  Time limit:    1 seconds  Memory limit:         512 megabytes  
  Aqua is five years now! She loves painting very much, and after day by day to paint, she finds a question:  
 
Can I paint the picture by just one stroke? 
 
In some other words, there are 𝑛 points in the picture and are connected by 𝑚 edges. She needs to find if she can paint the picture by one stroke, which means if she can paint all the edges in the picture by one stroke. 
 
Note that two unconnected points can’t be painted from one to another by one stroke, and every edge must only be painted once. 
 
You need to tell her if she can paint the picture by just one stroke, and if she can’t, tell her the minimum number of strokes she needs to paint the picture. Input 
The first line contains two integers 𝑛 (1 ≤ 𝑛 ≤ 200000) indicating the number of points and 𝑚 (1 ≤ 𝑚 ≤ 1000000) indicating the number of edges. 
 
Then followed by m lines each line contains two integers x, y indicating there is an edge between point 𝑥 and point 𝑦 (1 ≤ 𝑥,𝑦 ≤ 𝑛). 
 
It is guaranteed that there are no two completely identical edges.  Output 
If she can paint the picture by one stroke just print YES. 
 
Otherwise print NO, then followed by one line contains one integer, the minimum number of strokes she needs to paint all the points in the picture.

Sample input and output

Sample Input

4 5

1 2

1 3

1 4

Sample Output

YES 
 
2 3 3 4

Sample Input

5 5

1 2

2 3

2 4

3 4

4 5

Sample Output

NO 2

Note 
In the first test case, she can start with point 1 and paints by 1 → 2 → 3 → 4, so she can paint the picture by just one stroke, so the answer is YES. 
 
In the second test case, it is proved she can’t paint the picture by just one stroke and the minimum number of strokes is 2. One optional way to paint the picture is:  First stroke: 1 → 2 → 3 → 4 → 5 Second stroke: 2 → 4 
 
 题意：

一个无向图是否是一笔画，如果不是需要画几笔？

--------------------分---------------------割----------------------线-------------------

科普一下有关一笔画的问题（是否存在欧拉路）：

某无向图是否是一笔画？

（1）连通 && 奇度顶点数 == 0 （欧拉回路）

（2）连通 && 奇度顶点数 == 2 （欧拉路）

若某连通的无向图不是一笔画，奇度顶点数为 k，那么该图需要画 k / 2 笔

--------------------分--------------------割-----------------------线--------------------

思路：

这个题给的图有可能不是连通图，所以先求连通分量，再求每个连通分量的奇度顶点数，加起来就是答案。

正解用的带权并查集，在下面。

我的：（比赛时没过，赛后改的，没有补题的地方，我也不知道能不能AC....

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const int N = 2e5 + 10;

int d[N];///度
int n, m;
int pre[N];

void init(int n)
{
    for(int i = 1; i <= n; ++i)
    {
        pre[i] = i;
    }
}

int Find(int x)
{
    if(x == pre[x])
        return x;
    int fx = Find(pre[x]);
    return pre[x] = fx;
}

void join(int x, int y)
{
    int fx, fy;
    fx = Find(x);
    fy = Find(y);
    if(fx != fy)
    {
        pre[fx] = fy;
    }
}

int main()
{
    int u, v;
    scanf("%d%d", &n, &m);
    memset(d, 0, sizeof(d));
    init(n);
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d", &u, &v);
        join(u, v);
        d[u]++;
        d[v]++;
    }
    for(int i = 1; i <= n; ++i)
    {
        pre[i] = Find(i);
    }
    map<int, int>mp;    ///每个连通分量有多少个奇度顶点
    map<int, int>::iterator it;
    for(int i = 1; i <= n; ++i)
    {
        if(d[i] & 1)
            mp[pre[i]]++;
    }
    int ans = 0;
    for(it = mp.begin(); it != mp.end(); ++it)
    {
        if(it -> second == 0 || it -> second == 2)
            ans++;
        else
            ans += it -> second / 2;
    }
    if(ans == 1)
        cout<<"YES"<<'\n';
    else
    {
        cout<<"NO"<<'\n';
        cout<<ans<<'\n';
    }
    mp.clear();
    return 0;
}
/*
4 5
1 2
1 3
1 4
2 3
3 4
5 5
1 2
2 3
2 4
3 4
4 5
8 7
1 2
2 3
3 8
2 8
4 5
5 7
6 5
*/

带权并查集：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+7,M=1e6+7;
int n,m,fa[N],du[N],f[N],x[M],y[M];
int find(int x)
{
    if(x==fa[x])
        return x;
    else
        fa[x]=find(fa[x]);
    return fa[x];
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        du[x[i]]++;
        du[y[i]]++;
        f[x[i]]=1;
        f[y[i]]=1;     //判断点有连边
    }
    for(int i=1; i<=n; i++)
    {
        fa[i]=i;
        if(du[i]%2)
            du[i]=1;
        else
            du[i]=0; //把 du[i]转化成 1 为奇度点，0为偶度点
    }
    //方便下面并查集求连通分量内奇点总数
    for(int i=1; i<=m; i++)
    {
        int fx=find(x[i]),fy=find(y[i]);
        if(fx!=fy)
        {
            fa[fx]=fy;
            du[fy]+=du[fx];
        }
    }
    int ans=0;
    for(int i=1; i<=n; i++)
        if(f[i]&&find(i)==i)
            if(du[i]<2)
                ans++;
            else
                ans+=du[i]/2;
    if(ans==1)
        cout<<"YES";
    else
        cout<<"NO\n"<<ans;
}