Ant Trip

https://loj.ac/problem/10108

题目描述

  给出一张\(n\)个点，\(m\)条边的图，保证无重边和自环，求至少要几笔才能把所有边画一遍。

思路

  首先我们可以按每个连通块进行考虑，再把答案相加即可。而在每个点连通块内，如果度为奇数的点的个数小于等于\(2\)，显然可以一笔画完；而大于两个，我们一笔最多只能画完两个奇点所连得边，所以至少要\(\frac{cnt}{2}\)次。另外，对于孤立点无需考虑。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=4e5+10;

int nxt[M],head[N],to[M],tot;
void add_edge(int x,int y)
{
    nxt[++tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}

int read()
{
    int res=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+ch-'0';ch=getchar();}
    return res*w;
}

int cnt,deg[N];
bool vis[N];
void dfs(int u)
{
    vis[u]=1;
    if(deg[u]&1)cnt++;
    for(int i=head[u];i;i=nxt[i])
    {
        int v=to[i];
        if(!vis[v])dfs(v);
    }
}

void clear()
{
    memset(head,0,sizeof(head));
    memset(vis,0,sizeof(vis));
    memset(deg,0,sizeof(deg));
    tot=0;
}

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        clear();
        for(int i=1;i<=m;i++)
        {
            int x=read(),y=read();
            add_edge(x,y);add_edge(y,x);
            deg[x]++;deg[y]++;
        }
        int ans=0;
        for(int i=1;i<=n;i++)
            if(!vis[i])
            {
                if(!head[i])continue;
                cnt=0;
                dfs(i);
                if(cnt<=2)++ans;
                else ans+=cnt/2;
            }
        printf("%d\n",ans);
    }
}