【題意】：給出一個有n個頂點、m條邊的簡單無向連通圖，其中m為偶數。求一個邊的配對，使得每一對邊共用一個頂點。

【題解】：不得不說，這是一道非常好的圖論題目。該題運用了分治的思想，分治的思想大多數情況下都是在遞歸中實現的，這題也不例外。具體做法：對圖進行dfs，并且記錄每個點訪問的時間（dfn[I] 記錄 i 這個結點訪問的時間，跟tarjan算法那個類似），這里用pre記錄u的前驅，cur記錄v的后繼。具體思想是，假如找到一個v的后繼cur，那么意味我們找到一個配對u v cur；或者找到一個u的前驅，那么我們可以得到配對pre u v。具體操作看代碼吧，我不知道怎么表達出來。

【代碼】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 using namespace std;
 5 #define maxn 20005
 6 #define maxm 200005
 7 int n, m;
 8 int eh[maxn], dfn[maxn], Dindex, tot;
 9 struct Edge {
10     int v, next;
11 }et[maxm];
12 
13 void init() {
14     tot = 0;
15     memset(eh, -1, sizeof(eh));
16 }
17 
18 void addedge(int u, int v) {
19     Edge e = {v, eh[u]};
20     et[tot] = e;
21     eh[u] = tot++;
22 }
23 
24 int dfs(int u) {
25     int pre = -1;                //u的前驅
26     dfn[u] = ++Dindex;            //時間戳
27     for(int i = eh[u]; i != -1; i = et[i].next) {
28         int v = et[i].v;
29         if(!dfn[v]) {
30             int cur = dfs(v);    //v的后繼
31             if(cur != -1) printf("%d %d %d\n", u, v, cur);
32             else if(pre == -1) pre = v;
33             else {
34                 printf("%d %d %d\n", pre, u, v);
35                 pre = -1;
36             }
37         } else if(dfn[u] < dfn[v]) {
38             if(pre == -1) pre = v;
39             else {
40                 printf("%d %d %d\n", pre, u, v);
41                 pre = -1;
42             }
43         }
44     }
45     return pre;
46 }
47 
48 void solve() {
49     Dindex = 0;
50     memset(dfn, 0, sizeof(dfn));
51 //    for(int i = 1; i <= n; i++)        //因為題目說是連通圖，所以只需要從任意一個點dfs就能搜完整個圖
52 //        if(!dfn[i])
53             dfs(1);
54 }
55 int main() {
56     while(~scanf("%d%d", &n, &m)) {
57         init();
58         for(int i = 0; i < m; i++) {
59             int u, v;
60             scanf("%d%d", &u, &v);
61             addedge(u, v), addedge(v, u);
62         }
63         solve();
64     }
65     return 0;
66 }