有个显然的结论是对于一个\(m\)条边的连通图，一定可以划分成\(\lfloor{\frac{m}{2}}\rfloor\)个边的pair，使两边有公共顶点
那么奇数显然不行，偶数显然可以
我们考虑怎么构造：抓出一个dfs树，然后把每条边都附加到深度小的那个结点上
然后从叶子向上合并pair：如果该点有偶数个附加的边，那么两两配对；否则拿落单的那条边和父边配对，其余两两配对(这时候需要在父节点删掉这条边)
1 #include<bits/stdc++.h> 2 #define maxn 100005 3 using namespace std; 4 int n,m; 5 vector<int> g[maxn]; 6 struct node 7 { 8 int x,y,z; 9 node(int X=0,int Y=0,int Z=0):x(X),y(Y),z(Z){} 10 }; 11 vector<int> q[maxn]; 12 vector<node> ans; 13 bool vis[maxn]; 14 void dfs(int u,int f) 15 { 16 vis[u]=1; 17 for(int v:g[u])if(v!=f) 18 { 19 if(vis[v])q[v].push_back(u); 20 else dfs(v,u); 21 } 22 int sz=q[u].size(); 23 if(sz&1) 24 { 25 q[u].push_back(f); 26 for(int i=0;i<sz;i+=2)ans.push_back(node(q[u][i],u,q[u][i+1])); 27 } 28 else 29 { 30 for(int i=0;i<sz;i+=2)ans.push_back(node(q[u][i],u,q[u][i+1])); 31 q[f].push_back(u); 32 } 33 } 34 int main() 35 { 36 scanf("%d%d",&n,&m); 37 for(int u,v,i=1;i<=m;++i) 38 { 39 scanf("%d%d",&u,&v); 40 g[u].push_back(v); 41 g[v].push_back(u); 42 } 43 if(m&1) 44 { 45 puts("No solution"); 46 } 47 else 48 { 49 dfs(1,0); 50 for(int i=0;i<m/2;++i)printf("%d %d %d\n",ans[i].x,ans[i].y,ans[i].z); 51 } 52 }
原文：https://www.cnblogs.com/uuzlove/p/12295791.html
