Ant Trip

题目链接

• 题意：
  给定一个无向图，每条边只走一次，可以有多个出发点，最多要多少个出发点？（不考虑孤立点）
• 注意：
  孤立点不考虑；注意merge的时候的写法

const int MAXV = 120000;
const int MAXE = 220000;

int father[MAXV], num[MAXV], odd[MAXV];
int degree[MAXV];
void init()
{
    CLR(degree, 0);
    REP(i, MAXV)
    {
        father[i] = i;
        num[i] = 1;
        odd[i] = 0;
    }
}
int find(int n)
{
    return father[n] == n ? n : father[n] = find(father[n]);
}
void merge(int a, int b)
{
    int fa = find(a), fb = find(b);
    if (fa != fb)
    {
        father[fb] = fa;
        num[fa] += num[fb];
        odd[fa] += odd[fb];
    }
    if (++degree[a] % 2 != 0)
        odd[fa]++;
    else
        odd[fa]--;
    if (++degree[b] % 2 != 0)
        odd[fa]++;
    else
        odd[fa]--;
}
int main()
{
//    freopen("in.txt", "r", stdin);
    int v, e;
    while (~RII(v, e))
    {
        init();
        int a, b;
        REP(i, e)
        {
            RII(a, b);
            merge(a, b);
        }
        int ans = 0;
        FE(i, 1, v)
        {
            if (find(i) == i && num[i] != 1)
            {
                if (odd[i] <= 2)
                    ans++;
                else
                    ans += odd[i] / 2;
            }
        }
        WI(ans);
    }
    return 0;
}

Ant Trip,布布扣,bubuko.com

Ant Trip

原文：http://blog.csdn.net/wty__/article/details/21825993