uva 10054 The Necklace 拼項鏈 歐拉回路基礎應用

昨天做了道水題，今天這題是比較水的應用。

給出n個項鏈的珠子，珠子的兩端有兩種顏色，項鏈上相鄰的珠子要顏色匹配，判斷能不能拼湊成一天項鏈。

是挺水的，但是一開始我把整個項鏈看成一個點，然後用dfs去找，結果超時了。

後來瞄了一眼題解發現把顏色當成點，一個珠子就是一條路，這樣就能得到一個無向圖了，然後判斷歐拉回路即可。

這題默認是珠子為連通的，所以不需要判斷連通性。然後判斷節點的度數是否為偶數，也就是是否為歐拉回路，如果是的話用深搜輸出珠子的順序。深搜時輸出記得得放在遞歸之後，用逆序輸出，不然會出錯的，具體看Titanium大神的博客，他介紹的很清楚。（Orz）

代碼：

 
#include <cstdio>   
#include <cstring>   
const int maxn = 51;  
int t, n;  
int id[maxn], g[maxn][maxn];  
  
void euler(int u) {  
    for (int i = 1; i <= 50; i++)   
        if (g[u][i]) {  
            g[u][i]--;  
            g[i][u]--;  
            euler(i);  
            printf("%d %d\n", i, u);  
        }  
}  
  
int main() {  
    scanf("%d", &t);  
    int a, b;  
    for (int cas = 1; cas <= t; cas++) {  
        scanf("%d", &n);  
        memset(id, 0, sizeof(id));  
        memset(g, 0, sizeof(g));  
        for (int i = 0; i < n; i++) {  
            scanf("%d%d", &a, &b);  
            g[a][b]++;  
            g[b][a]++;  
            id[a]++;  
            id[b]++;  
        }  
        int i;  
        for (i = 1; i <= 50; i++)  
            if (id[i] % 2)  
                break;  
        if (cas > 1)  
            printf("\n");  
        printf("Case #%d\n", cas);  
        if (i <= 50)  
            printf("some beads may be lost\n");  
        else  
            for (i = 0; i <= 50; i++)  
                euler(i);  
    }//for   
    return 0;  
}  

#include <cstdio>
#include <cstring>
const int maxn = 51;
int t, n;
int id[maxn], g[maxn][maxn];

void euler(int u) {
	for (int i = 1; i <= 50; i++) 
		if (g[u][i]) {
			g[u][i]--;
			g[i][u]--;
			euler(i);
			printf("%d %d\n", i, u);
		}
}

int main() {
	scanf("%d", &t);
	int a, b;
	for (int cas = 1; cas <= t; cas++) {
		scanf("%d", &n);
		memset(id, 0, sizeof(id));
		memset(g, 0, sizeof(g));
		for (int i = 0; i < n; i++) {
			scanf("%d%d", &a, &b);
			g[a][b]++;
		   	g[b][a]++;
			id[a]++;
		   	id[b]++;
		}
		int i;
		for (i = 1; i <= 50; i++)
			if (id[i] % 2)
				break;
		if (cas > 1)
			printf("\n");
		printf("Case #%d\n", cas);
		if (i <= 50)
			printf("some beads may be lost\n");
		else
			for (i = 0; i <= 50; i++)
				euler(i);
	}//for
	return 0;
}