【题意】：给出一个有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 }