Ant Trip 解題報告：無向圖邊覆蓋與奇點配對

問題建模

給定無向圖，每條邊必須恰好走一次，可有多個起點，求最少起點數（忽略孤立點）。這等價於：將圖分解為若干條路徑（不一定是簡單路徑），使得每條邊屬於恰好一條路徑，最小化路徑條數。

圖論結論

• 連通圖中，若奇度頂點數為 0，存在歐拉迴路，1 條路徑覆蓋所有邊。
• 若奇度頂點數為 2k (k>0)，最少需 k 條路徑（每條路徑消耗 2 個奇點）。
• 偶度頂點可作為路徑內部點，不增加路徑數。

對於森林（多連通塊），各連通塊獨立計算，總和即為答案。

算法流程

1. 用並查集維護連通塊，統計每個塊的頂點數 num[] 和奇度數 odd[]。
2. 讀入邊時合併並查集，更新雙端點度數奇偶性，同步維護 odd[]。
3. 遍歷所有代表元：若 num[i] > 1（非孤立點），則 ans += max(1, odd[i]/2)。

關鍵代碼

const int MAXV = 120000;
int father[MAXV], num[MAXV], odd[MAXV], deg[MAXV];

void init() {
    fill(deg, deg+MAXV, 0);
    for (int i=0;i<MAXV;++i) father[i]=i, num[i]=1, odd[i]=0;
}
int find(int x) { return father[x]==x?x:father[x]=find(father[x]); }

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 (++deg[a]%2) odd[fa]++; else odd[fa]--;
    if (++deg[b]%2) odd[fa]++; else odd[fa]--;
}

int main() {
    int v, e;
    while (~scanf("%d%d",&v,&e)) {
        init();
        for (int i=0;i<e;++i) { int a,b; scanf("%d%d",&a,&b); merge(a,b); }
        int ans=0;
        for (int i=1;i<=v;++i)
            if (find(i)==i && num[i]!=1)
                ans += (odd[i]<=2)? 1 : odd[i]/2;
        printf("%d\n", ans);
    }
}

注意事項

• 並查集合併時必須先合併集合，再更新 odd，否則屬於不同集合的奇點計數會錯亂。
• 孤立點（num==1）不計入答案，題目明確要求忽略。
• 度數更新邏輯：度數變奇則 odd++，變偶則 odd--。