hdu 3018(无向图) | yusijia's blog

Contents

1. Problem Description
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Hint
7. 题目大意：
8. 分析：

Problem Description

Ant Country consist of N towns.There are M roads connecting the towns.

Ant Tony,together with his friends,wants to go through every part of the country.

They intend to visit every road , and every road must be visited for exact one time.However,it may be a mission impossible for only one group of people.So they are trying to divide all the people into several groups,and each may start at different town.Now tony wants to know what is the least groups of ants that needs to form to achieve their goal.

Input

Input contains multiple cases.Test cases are separated by several blank lines. Each test case starts with two integer N(1<=N<=100000),M(0<=M<=200000),indicating that there are N towns and M roads in Ant Country.Followed by M lines,each line contains two integers a,b,(1<=a,b<=N) indicating that there is a road connecting town a and town b.No two roads will be the same,and there is no road connecting the same town.

Output

For each test case ,output the least groups that needs to form to achieve their goal.

Sample Input

3 3
1 2
2 3
1 3

4 2
1 2
3 4

Sample Output

1
2

Hint

New ~~~ Notice: if there are no road connecting one town ,tony may forget about the town.
In sample 1,tony and his friends just form one group,they can start at either town 1,2,or 3.
In sample 2,tony and his friends must form two group.

题目大意：

N个点m条边的无向图，每条边只能走一遍，求有几条欧拉道路或欧拉回路。可以简单的理解为要几笔才能画完整个图。

分析：

如果有n个连通分量，则至少有n条欧拉回路或欧拉通路，
首先通过并查集确定有几个连通分量，(利用set的特性只存连通分量里的祖先节点，用这个节点来代表当前连通分量)
然后看每个连通分量里有几条欧拉回路和欧拉通路，可以通过度数判断，如果都是偶数，则有欧拉回路，如果有奇数点，则欧拉通路的个数为(奇数点个数 + 1) / 2(开一个num[]数组来记录连通分量里的奇数点的个数)

　　最后注意一下题目的小提示，如果有孤立的点(没有边到达的点),就忽略他，所以要开一个vis[]标记数组记录一下那些点是连通的。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

const int MAXN = 100010;

int father[MAXN], degree[MAXN], n, m, num[MAXN];
bool vis[MAXN];

void init()
{
    memset(degree, 0, sizeof(degree));
    memset(vis , false , sizeof(vis));
    memset(num, 0, sizeof(num));
    for(int i = 0; i < MAXN; i++)
        father[i] = i;
}

int finds(int x)
{
    return x == father[x] ? father[x] : father[x] = finds(father[x]);
}

void unions(int x, int y)
{
    int root_x = finds(x);
    int root_y = finds(y);
    father[root_x] = root_y;
}

int solve()
{
    int sum = 0;
    set<int> s;
    s.clear();
    for(int i = 1; i <= n; i++)if(vis[i]){
        s.insert(finds(i));//存连通分量的祖先节点
    }
    for(int i = 1; i <= n; i++){
        if(degree[i] % 2 == 1)
            num[finds(i)]++;//记录连通分量里度数为奇数的点的个数
    }
    for(set<int>::iterator it = s.begin(); it != s.end(); it++){
        if(!num[*it])
            sum++;//如果该连通分量里点的度数都为偶数(每个点度数为偶数，祖先又都是同一个点)，则为欧拉回路
        else
            sum += (num[*it] + 1) / 2;//否则可分为几条欧拉通路
    }
    return sum;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int x, y;
    while(scanf("%d%d", &n, &m) != EOF){
        init();
        for(int i = 0; i < m; i++){
            scanf("%d%d", &x, &y);
            degree[x]++;
            degree[y]++;
            vis[x] = true;
            vis[y] = true;
            unions(x, y);
        }
        printf("%d\n", solve());
    }

    return 0;
}