UVa 12118 检查员的难题 （dfs判连通， 构造欧拉通路）

题意：

分析：

欧拉通路:图连通；图中只有0个或2个度为奇数的结点

这题我们只需要判断选择的边构成多少个联通块， 再记录全部联通块一共有多少个奇度顶点。

然后我们在联通块中连线， 每次连接两个联通块就减少2个奇度顶点， 然后再数一下剩下的奇度顶点odd（肯定是剩下偶数个）， 因为存在两个奇度顶点的图也是欧拉通路， 我们只需要在（odd - 2）个顶点中连线使其变为偶度顶点即可。

如果本身就没有奇度顶点就不需要除了。

所以答案就是 T * （E  +（联通块 - 1） + （odd - 2）/ 2））

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 int V, E, T;

 vector<int> G[maxn];

 set<int> pick;

 int deg[maxn];

 bool vis[maxn];

 void dfs(int u){

     vis[u] = ;

     for(int i = ; i < G[u].size(); i++){

         if(!vis[G[u][i]]){

             dfs(G[u][i]);

         }

     }

 }

 int main(){

     int kase = ;

     while(scanf("%d %d %d", &V, &E, &T) && V){

         memset(deg,, sizeof(deg));

         memset(vis, , sizeof(vis));

         pick.clear();

         for(int i = ; i < E; i++){

             int u, v;

             scanf("%d %d", &u, &v);

             deg[u]++, deg[v]++;

             G[u].push_back(v);

             G[v].push_back(u);

             pick.insert(v);

             pick.insert(u);

         }

         int part = ;

         int odd = , even = ;

         for(auto it = pick.begin(); it != pick.end(); it++){

             if(!vis[*it]){

                 dfs(*it);

                 part++;

             }

             if(deg[*it] %  == ){

                 even++;

             }

             else odd++;

             G[*it].clear();

         }

         odd -= (part - ) * ;

         int ans = E + part - ;

         if(odd > ){

                 ans += (odd -)/;

         }

         if(E == ) ans = ;//特判一下没有边的情况

         printf("Case %d: %d\n",kase++, ans * T);

     }

     return ;

 }