Ant Trip HDU - 3018

周一(10.15) TEST<18>

A - Ant Trip HDU - 3018

解题思路 并查集 + 欧拉回路

基础 并查集模板
欧拉回路 : 走完图的所有边(回到起点) (欧拉图)
欧拉通路:走完图的所有顶点(无需回到起点)(半欧拉图)

欧拉性质 : 1.有零个奇点 ,存在欧拉回路
2.有零个或两个奇点 ,存在欧拉通路
(半)欧拉图只需要一笔// 非(半/欧拉)图 奇点数/2;

AC代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int m=1e5+10;
int pre[m],ans[m],dep[m];
int n,t;
void init(){//初始化函数
    for(int i=0;i<=n;i++)
    pre[i]=i;
    memset(ans,0,sizeof(ans));
    memset(dep,0,sizeof(dep));
}
int find(int x){//路径压缩
    if(pre[x]!=x)
     x=find(pre[x]);
    return  x;
}
void build(int x,int y){//并查集建树
    int a=find(x);
    int b=find(y);
    if(a!=b)
    pre[a]=b;
}
int main(){
    while(cin>>n>>t){
    init();
        for(int i=0;i<t;i++){
            int x,y;
            cin>>x>>y;
            dep[x]++;//统计分支
            dep[y]++;
            build(x,y);
        }
        int sum=0;//统计笔画参数
        for(int i=1;i<=n;i++)
        if(deg[i]%2){//奇点数
            ans[find(i)]++;// 累加至所指 根
            sum++;//统计
        }
        sum/=2;//上文提到的性质
        for(int i=1;i<=n;i++)
        if(find(i)==i){//根未统计
            if(ans[i]==0&&dep[i]!=0])
            //欧拉回路并且不为 一个单独的点(题目中不统计)
            sum++;
        }
        cout<<sum<<endl;
    }
    return 0;
}