hdu3018 Ant Trip【欧拉图】

想回家种地的码农 lv.1

发布时间：2022-11-28 10:55:29 324

相关标签： # php

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3018
题意：给你n个点，m条边，问你几笔能画完所有边
解析：首先这个图不连通，所以要分成几块来计算，每一块都有三种情况，如果是个欧拉图，那就一笔画玩，如果是孤立点那就不管，如果是其他的，那就输有几个度数为奇数的点，奇点/2就是总笔画数，所以ans = 奇点/2+欧拉图个数

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e5+100;
int fa[maxn],odd[maxn];
int du[maxn],vis[maxn];
vectortmp;
void init(int n)
{
    memset(odd,0,sizeof(odd));
    memset(vis,0,sizeof(vis));
    memset(du,0,sizeof(du));
    for(int i=0;i<=n;i++)
        fa[i] = i;
    tmp.clear();
}
int getFa(int x)
{
    if(x==fa[x])
        return x;
    return fa[x] = getFa(fa[x]);
}
void merge(int u,int v)
{
    int t1 = getFa(u);
    int t2 = getFa(v);
    if(t1!=t2)
        fa[t1] = t2;
}
int main(void)
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        init(n);
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d %d",&u,&v);
            merge(u,v);
            du[u]++,du[v]++;
        }
        for(int i=1;i<=n;i++)
        {
            int fa = getFa(i);
            if(!vis[fa])
            {
                vis[fa] = 1;
                tmp.push_back(fa);
            }
            if(du[i]%2)
                odd[fa]++;
        }
        int ans = 0;
        for(unsigned i = 0;i<tmp.size();i++)
        {
            if(du[tmp[i]]==0)
                continue;
            if(odd[tmp[i]]==0)
                ans++;
            else
                ans += odd[tmp[i]]/2;
        }
        printf("%d\n",ans);
    }
    return 0;
}

文章来源： https://blog.51cto.com/u_11435021/5880206

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。