cf860D Wizard's Tour

给一个图,要求你找出尽可能多的长度为2的路径,他们没有重复的边,输出路径数和这些路径

考虑一棵树的情况,对于一个叶子的直系父亲,如果他有偶数个儿子那么所有的儿子都能在这个点处匹配成长度为2的路径;若它有奇数个儿子一定有个儿子被留下来了,那就只能取 这个儿子-儿子的父亲(就是这个结点)-儿子的父亲的父亲 这条路了。这样贪心的匹配一定使得树由下至上尽可能没有浪费的边。

对于一个不是树的无向图的话,因为真正对答案有贡献的肯定是边,点重复了没有影响,那么对于长度为$len$环,考虑对重复走到的点新建一个结点,把环剪开成一个有$len+1$个点的链(多加的那个点是新建的结点),然后这个图就变成一颗树辣。

得到树以后由下到上按之前的策略贪心即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include <bits/stdc++.h>
using namespace std;
const int maxn=2*100000+5;
inline int readint()
{
char c;int tmp=0,x=1;c=getchar();
while(!isdigit(c)){if(c=='-') x=-1;c=getchar();}
while(isdigit(c)){tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
int tot=0,extr=0,head[2][maxn*5],ed[2][maxn*5],nxt[2][maxn*5],n,m,sons[maxn*5];
void addedge(int id,int from,int to)
{
assert(to!=0);assert(from!=0);
ed[id][tot]=to;nxt[id][tot]=head[id][from];head[id][from]=tot;tot++;
ed[id][tot]=from;nxt[id][tot]=head[id][to];head[id][to]=tot;tot++;
}
bool vis[maxn*5],edvis[maxn*5],lev[maxn*5];
int cnt[maxn*5];
struct trio{int u,v,w;
trio(int u=0,int v=0,int w=0): u(u),v(v),w(w) {}
};
vector<trio > Ege;
#define MP make_pair
map<int ,int > rfl;
void dfs(int v)
{
vis[v]=true;
for(int i=head[0][v];i!=-1;i=nxt[0][i]){
if(edvis[i]) continue;
edvis[i]=edvis[i^1]=true;
int u=ed[0][i];
if(vis[u]) addedge(1,v,++extr),rfl[extr]=u;
else {addedge(1,v,u);dfs(u);}
sons[v]++;
}
}
vector<pair<int ,int> > aoi[maxn*5];
vector<int > shiroi[maxn*5];
void Perform(int v)
{
vis[v]=true;
int rest=0;
aoi[v].clear();shiroi[v].clear();
for(int i=head[1][v];i!=-1;i=nxt[1][i]){
int u=ed[1][i];
if(!vis[u]) {
Perform(u);
rest+=lev[u];
cnt[v]+=cnt[u];
if(lev[u]) {
aoi[v].push_back(MP(u,shiroi[u].back()));
shiroi[u].pop_back();
assert(shiroi[u].empty());
}else shiroi[v].push_back(u);
}
}
int left=sons[v]-rest,U,V;
for(int i=1;i<=rest;i++){
Ege.push_back(trio(v,aoi[v][i-1].first,aoi[v][i-1].second));
}
for(int i=1;i<=left/2;i++){
U=shiroi[v].back(),shiroi[v].pop_back();
V=shiroi[v].back(),shiroi[v].pop_back();
Ege.push_back(trio(U,v,V));
}
assert((int)shiroi[v].size()<=1);
cnt[v]+=left/2+rest;lev[v]=(left&1);
}
int Change(int v){if(v>n) return rfl[v];else return v;}
int main()
{
n=readint(),m=readint();
extr=n;
int u,v;
memset(head,-1,sizeof(head));memset(nxt,-1,sizeof(nxt));
for(int i=1;i<=m;++i)
u=readint(),v=readint(),addedge(0,u,v);
for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
memset(vis,0,sizeof(vis[0])*(extr+1));
int ans=0;
for(int i=1;i<=extr;i++)
if(!vis[i]) {Perform(i);ans+=cnt[i];}
printf("%d\n",ans);
for(int i=0;i<(int)Ege.size();i++){
Ege[i].v=Change(Ege[i].v),Ege[i].u=Change(Ege[i].u),Ege[i].w=Change(Ege[i].w);
}
for(int i=0;i<(int)Ege.size();i++) printf("%d %d %d\n",Ege[i].u,Ege[i].v,Ege[i].w);
return 0;
}