sgu 286. Ancient decoration（最小環覆蓋）

給你一個n個點，每個點度為k（k為偶數）的無向圖，問是否能將圖中的n條邊染色，使得每個點都擁有兩條被染色的邊。也就是說，是否存在擁有原圖中n條邊的子圖，使得每個點的度為2？仔細想想，每個點的度為2，實際上就是求原圖的最小環覆蓋了。   求最小環覆蓋的方法就是先求出原圖的有向歐拉回路（k為偶數，歐拉回路必然存在），然後問題就轉化成了是否能選擇歐拉回路中的n條邊，使得所有點都被覆蓋？這不就轉化成了DAG的最小路徑覆蓋了麼！      

#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<cstdlib>  
#include<fstream>  
#include<sstream>  
#include<bitset>  
#include<vector>  
#include<string>  
#include<cstdio>  
#include<cmath>  
#include<stack>  
#include<queue>  
#include<stack>  
#include<map>  
#include<set>  
#define FF(i, a, b) for(int i=a; i<b; i++)  
#define FD(i, a, b) for(int i=a; i>=b; i--)  
#define REP(i, n) for(int i=0; i<n; i++)  
#define CLR(a, b) memset(a, b, sizeof(a))  
#define debug puts("**debug**")  
#define LL long long  
#define PB push_back  
using namespace std;  
  
const int maxn = 1001;  
int g[maxn][maxn], degree[maxn], match[maxn], id[maxn][maxn];  
bool vis[maxn];  
int n, k, u, v;  
  
void Euler()  
{  
    FF(i, 1, n+1) if(degree[i])  
    {  
        int u = i;  
        while(true)  
        {  
            FF(j, 1, n+1) if(g[u][j] && g[j][u])  
            {  
                g[j][u] = 0;  
                degree[u]--, degree[i]--;  
                u = j;  
                break;  
            }  
            if(u == i) break;  
        }  
    }  
}  
  
bool dfs(int u)  
{  
    FF(i, 1, n+1) if(!vis[i] && g[u][i])  
    {  
        vis[i] = true;  
        if(match[i] == 0 || dfs(match[i]))  
        {  
            match[i] = u;  
            return true;  
        }  
    }  
    return false;  
}  
  
bool max_match()  
{  
    CLR(match, 0);  
    FF(i, 1, n+1)  
    {  
        CLR(vis, 0);  
        if(!dfs(i)) return false;  
    }  
    return true;  
}  
  
int main()  
{  
    while(~scanf("%d%d", &n, &k))  
    {  
        CLR(degree, 0);CLR(g, 0);  
        REP(i, n*k/2)  
        {  
            scanf("%d%d", &u, &v);  
            g[u][v] = g[v][u] = 1;  
            id[u][v] = id[v][u] = i+1;  
            degree[u]++, degree[v]++;  
        }  
        Euler();  
        if(max_match())  
        {  
            puts("YES");  
            FF(i, 1, n+1) printf("%d\n", id[match[i]][i]);  
        }  
        else puts("NO");  
    }  
    return 0;  
}