UVA 12118 - Inspector's Dilemma ( Euler's Path )

UVa Online Judge
First, we observe that if we have x connected components, we will have to connect them with x - 1 extra edges, whereas such connected components are only limited to those with vertices that at least involve in one edge. Well, a special case is obviously when there are no edges, which means there are 0 connected components thus the answer will be 0. Next, let's see how many edges we will need to run through all edges in any particular connected component. Euler's path gives us the conclusion that if there are exactly 0 or 2 odd-degree vertices, it is possible to run through each edge exactly once. A subtle detail here is that the number of odd-degree vertices will always be even. Then, we will realise that if the number of odd-degree vertices is greater than 2, we will have to connect them pair by pair, which makes ( odd, odd ) -> ( even, even ), so it will satisfy the Euler's path conclusion.

#include <bits/stdc++.h>
using namespace std;

const int MAXV = 1e3 + 3;

struct UnionFind{
    int fa[ MAXV ];
    void init(){
        for( int i = 1; i < MAXV; ++i )
            fa[ i ] = 0;
    }
    int find( int x ){
        if( fa[ x ] == x ) return x;
        return fa[ x ] = find( fa[ x ] );
    }
    bool unite( int x, int y ){
        int a = find( x );
        int b = find( y );
        if( a == b ) return false;
        fa[ a ] = b; return true;
    }
} uf;

int kase;

int V, E, T;
int deg[ MAXV ];
int odd_deg_cnt[ MAXV ];

bool solve(){
    cin >> V >> E >> T; if( V + E + T == 0 ) return false;
    cout << "Case " << ++kase << ": ";
    int ans = E, cc_cnt = 0;
    uf.init();
    memset( deg, 0, sizeof( deg ) );
    memset( odd_deg_cnt, 0, sizeof( odd_deg_cnt ) );
    for( int i = 0; i < E; ++i ){
        int u, v; cin >> u >> v;
        if( uf.fa[ u ] == 0 ) uf.fa[ u ] = u, ++cc_cnt;
        if( uf.fa[ v ] == 0 ) uf.fa[ v ] = v, ++cc_cnt;
        if( uf.unite( u, v ) ) --cc_cnt;
        ++deg[ u ], ++deg[ v ];
    }
    for( int i = 1; i <= V; ++i )
        if( deg[ i ] & 1 )
            ++odd_deg_cnt[ uf.find( i ) ];
    for( int i = 1; i <= V; ++i )
        if( odd_deg_cnt[ i ] >= 4 )
            ans += odd_deg_cnt[ i ] / 2 - 1;
    if( cc_cnt == 0 ) cout << 0 << "\n";
    else cout << T * ( ans + cc_cnt - 1 ) << "\n";
    return true;
}

int main(){
    ios::sync_with_stdio( false );
    while( solve() );
    return 0;
}