CF858F Wizard’s Tour 题解【DFS树】【贪心】【构造】

点击量：208

    应用DFS树来构造答案的一道题。

目录

Description

All Berland residents are waiting for an unprecedented tour of wizard in his Blue Helicopter over the cities of Berland!

It is well-known that there are \(n\) cities in Berland, some pairs of which are connected by bidirectional roads. Each pair of cities is connected by no more than one road. It is not guaranteed that the road network is connected, i.e. it is possible that you can’t reach some city from some other.

The tour will contain several episodes. In each of the episodes:

• the wizard will disembark at some city \(x\) from the Helicopter;
• he will give a performance and show a movie for free at the city \(x\);
• he will drive to some neighboring city \(y\) using a road;
• he will give a performance and show a movie for free at the city \(y\);
• he will drive to some neighboring to \(y\) city \(z\);
• he will give a performance and show a movie for free at the city \(z\);
• he will embark the Helicopter and fly away from the city \(z\).
• It is known that the wizard doesn’t like to use roads, so he agrees to use each road at most once (regardless of direction). In other words, for road between \(a\) and \(b\) he only can drive once from \(a\) to \(b\), or drive once from \(b\) to \(a\), or do not use this road at all.

The wizards wants to plan as many episodes as possible without violation the above rules. Help the wizard!

Please note that the wizard can visit the same city multiple times, the restriction is on roads only.

Input

The first line contains two integers \(n, m (1\le n\le 2\cdot 10^5, 0\le m\le 2\cdot 10^5)\) — the number of cities and the number of roads in Berland, respectively.

The roads description follow, one in each line. Each description is a pair of two integers \(a_i, b_i (1\le a_i, b_i ≤ n, a_i\not= b_i)\), where \(a_i\) and \(b_i\) are the ids of the cities connected by the \(i\)-th road. It is guaranteed that there are no two roads connecting the same pair of cities. Every road is bidirectional. The cities are numbered from \(1\) to \(n\).

It is possible that the road network in Berland is not connected.

Output

In the first line print \(w\) — the maximum possible number of episodes. The next \(w\) lines should contain the episodes in format \(x, y, z\) — the three integers denoting the ids of the cities in the order of the wizard’s visits.

Examples

input

4 5
1 2
3 2
2 4
3 4
4 1

output

2
1 4 2
4 3 2

input

5 8
5 3
1 2
4 5
5 1
2 5
4 3
1 4
3 2

output

4
1 4 5
2 3 4
1 5 3
5 2 1

OI版题目描述

给定一张\(n\)个点\(m\)条边的无向图，每条边连接两个顶点，保证无重边自环，不保证连通。

你想在这张图上进行若干次旅游，每次旅游可以任选一个点\(x\)作为起点，再走到一个与\(x\)直接有边相连的点\(y\)，再走到一个与\(y\)直接有边相连的点\(z\)并结束本次旅游。

作为一个旅游爱好者，你不希望经过任意一条边超过一次，注意一条边不能即正向走一次又反向走一次，注意点可以经过多次，在满足此条件下，你希望进行尽可能多次的旅游，请计算出最多能进行的旅游次数并输出任意一种方案。

样例同上

说明

对于前\(20\%\)的数据，\(n\le 10, m\le 20\)；
对于另\(20\%\)的数据，\(m=n -1\)，并且图连通；
对于另\(10\%\)的数据，每个点的度数不超过\(2\)；
对于\(100\%\)的数据，\(n\le 100000; m\le 200000\)。

题解：

    这道题如果不输出方案，应该可以看出来答案是\(\sum_{连通块}\left\lfloor\frac{节点个数}2\right\rfloor\)。也就是说最多有一条边没有被经过，尝试用反证法说明：如果一个连通块中同时存在两条没有被经过的边，那么这两条边可以通过在图上的替代转移到一起。意思是这两条边既然在一个连通块内，也一定在同一条链上。那么我们就可以通过改变这条链上的状态来让这两条边移动到一起，如下图。

    被同种颜色覆盖的就是同一条路径，此时发现有两条单独的边没有被覆盖，此时我们可以移动红色的边到下面一条边上来，这样就构造出了连通的“\(x,y,z\)”。也就是把相邻的已被覆盖的路径转一条到空边上来，每次边移动一个单位，两条链总能到一起的:>。通过这种方法，可以说明当连通块中有偶数条边时，他们是可以全部配对的。当有奇数条时就需要让某一条落单了，因此每个连通块的贡献是\(\left\lfloor\frac{节点个数}2\right\rfloor\)。

    接下来介绍怎么构造这个题的答案。在后面的中文题面中，给出了一档部分分，即给定的图是一棵树。这样我们dfs它，回溯过程中转移，实质上有点像树形dp了，但是没有决策。如果它的度为奇数，那么把除了指向父亲的边以外的边两两配对组合答案，指向父亲的边不变；否则把所有的边（包括指向父亲的）都两两配对，指向父亲的边删掉即可。

    那么如果是一个图，并且不保证连通呢？如果我们按照上面证明的方法把边一条一条地移动，实在很复杂，而且编程复杂度也高。这个问题可以被转化到生成树上去做，我们dfs一遍这个图，可以生成一个dfs森林，对于每一棵dfs树，它可以像上面给出的树那样去做；但是它既然作为一个图，就有非树边，考虑怎么处理非树边。

    因为在dfs过程中，先做深度较大的节点，再做深度较小的节点，因此是无后效性的（虽然它依然不是DP）。我们在一个节点的dfs做完之后再更新与它有关的边，此时可以发现，在处理的过程中，把非树边和树边一起当作需要被删掉的边，删掉的边由于会遍历多次，所以要打上usedtag，同时因为dfs是在树边上进行的，那么树边是可以动态变化的，如果这个点的度（只计算没有used的边）为偶数，那么全部配对，否则留下树上父亲引进的入边，把剩下的配对。因为在dfs的过程中，可以保证父亲节点是没有进行处理的，所以改变父亲节点的状态是没有影响的。像这样dfs每个连通块，如果边数为奇数，那么dfs树的根节点会多出一条边（这是不可避免的），如果是偶数，会全部匹配，即最后处理根节点时，它的度一定是个偶数。

    最后输出答案即可。时间复杂度\(O(n+m)\)。

Code：

#include<cstdio>
#include<cstring>
struct edge
{
    int n,nxt,used;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
        used=0;
    }
    edge(){}
}e[400100];
int head[200100],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int ans[200100][3],acnt=0;
void addans(int x,int y,int z)
{
    ++acnt;
    ans[acnt][0]=x;
    ans[acnt][1]=y;
    ans[acnt][2]=z;
}
int used[200100];
void dfs(int x,int from)
{
    used[x]=1;
    for(int i=head[x];~i;i=e[i].nxt)
        if(!used[e[i].n])
            dfs(e[i].n,x);
    int cnt=0;
    for(int i=head[x];~i;i=e[i].nxt)
        if(!e[i].used)
            ++cnt;
    int a=0;
    for(int i=head[x];~i;i=e[i].nxt)
        if(((cnt&1)==0||e[i].n!=from)&&!e[i].used)
            if(a)
            {
                e[i].used=1;
                e[i^1].used=1;
                addans(a,x,e[i].n);
                a=0;
            }
            else
            {
                a=e[i].n;
                e[i].used=1;
                e[i^1].used=1;
            }

}
int main()
{
    memset(head,-1,sizeof(head));
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    for(int i=1;i<=n;++i)
        if(!used[i])
            dfs(i,i);
    printf("%d\n",acnt);
    for(int i=1;i<=acnt;++i)
    {
        for(int j=0;j<=2;++j)
            printf("%d ",ans[i][j]);
        puts("");
    }
    return 0;
}