题解：P11486 「Cfz Round 5」Mata rainen

· · 题解

首先先考虑什么时候是无解的。数据无解当且仅当有环（重边也算作环）。树是没有环的，所以在树上把环压成链必然会导致路径重复。

现在我们可以想想怎么构造这棵树。下面默认数据中没有环。
首先，当 m = n-1 时，构造是最简单的：直接把这些边输出就可以了。这启示我们这样做：尽量把所有输入的点对变成最后树上的边。

但是，如果用点对直接建成树，可能会有一些点没有被加进树里。例如：

6 3
1 2
1 3
1 5

解决方法：我们发现，把一条边变成一条链也是可以的。那么这些没有加进树的点就可以直接塞进某一条边中：

Yes
1 2
1 3
1 4
4 6
6 5

这里在边 1 5 中塞进了点 4 和 6，变成了后三行。

下一个问题：如果输入的点对之间不连通怎么办？（就像样例1）
参考刚才的方法。直接将后来的树的根塞进前面树的一条边中。

#include <bits/stdc++.h> 
using namespace std;
namespace llamn{
int n,m,i,j,k,t1,t2; 

struct eggy{int to,lst;};
struct eggy e[600100];
int h[300100], cnt;
void add(int u, int w);

bitset <300100> xv;
void dfs(int d, int f); //判断环

bitset<300100> ved,t;
int ped, ansl[300100], ansr[300100];
void adde(int v); //在准备输出的树中的最新一条边中插入点v 
void dfs_ans(int d, int f); 

int s[300100], tp;

#define mk_pair(a,b) ((((long long)(a))<<30)+(b))
unordered_set<long long> qq;
int main()
{
    scanf("%d%d",&n,&m); 
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d",&t1,&t2);
        t[t1] = 1, t[t2] = 1;
        add(t1,t2); add(t2,t1);

        if (qq.find(mk_pair(t1,t2)) != qq.end()) //判断重边 
        {
            puts("No");
            return 0;
        }qq.insert(mk_pair(t1,t2));
    }
    for (i = 1; i <= n; i++)
    {
        if (!xv[i]) dfs(i,0); //上下这两行没有关联 
        if (!t[i]) s[++tp] = i; //记录哪些点从未出现 
    }puts("Yes");
    for (i = 1; i <= n; i++)
    {
        if (!t[i]) continue;
        if (ved[i]) continue;
        if (ped) adde(i); //把新树的树根塞进上一棵树的边中 
        dfs_ans(i,-1);
    }for (i = 1; i <= tp; i++) //把没有出现的点塞进一条边中 
    {
        adde(s[i]);
    }
    for (i = 1; i <= ped; i++)
    {
        printf("%d %d\n",ansl[i], ansr[i]);
    }
    return 0;
}
void add(int u, int w)
{
    e[++cnt].to = w;
    e[cnt].lst = h[u];
    h[u] = cnt;
}void dfs(int d, int f)
{
    xv[d] = 1;
    for (int i = h[d]; i; i = e[i].lst)
    {
        if (e[i].to == f) continue;
        if (xv[e[i].to])
        {
            puts("No");
            exit(0);
        }dfs(e[i].to,d);
    }   
}void dfs_ans(int d, int f)
{
    ved[d] = 1;
    for (int i = h[d]; i; i = e[i].lst)
    {
        if(e[i].to == f) continue;
        ansl[++ped] = d; ansr[ped] = e[i].to;
        dfs_ans(e[i].to,d);
    }
}void adde(int v)
{
    t1 = ansr[ped];
    ansr[ped] = v;
    ansl[++ped] = v;
    ansr[ped] = t1;
}

}int main(){llamn::main();return 0;}

/*
元梦树上元梦果，元梦树下我放火
*/