CodeForces1477D Nezzar and Hidden Permutations（构造+调整+菊花图）_菊花图(编程)

problem

洛谷链接

题意：给定 $m$ 条形如 $(u,v)$ 的限制，要求 $a_u,a_v$ 的相对大小关系与 $b_u,b_v$ 相同。

且尽可能减少 $a_i=b_i$ 的数量，输出 $a,b$ 两个排列。

solution

我们考虑将每条 $(u,v)$ 限制转化成图 $G$ 中的一条边。

如果某个点 $i$ 的边数 $=n-1$，则一定有 $a_i=b_i$。（$n$ 为当前剩余点的数量）

边数等于点数减一，这说明点 $i$ 与其它所有点都有一定的要求，假设要求 $b_i>b_k$ 的 $k$ 有 $x$ 个，则 $a_i>a_k^{\prime }$ 的 $k^{\prime }$ 也等于 $x$。

这种确定的点直接按死不参与后面的讨论了。

那么到这里就剩下了一堆边数 $<n-1$ 的点了。

反转边的定义，$\bar{G}=E-G$，如果 $(u,v)$ 在 $\bar{G}$ 为一条边当且仅当 $(u,v)$ 原来是没有限制的。

这些点都是没有满边的，所以一定会跟至少一个其它点连边的。

$\bar{G}$ 形成的是一个生成树森林，没有必要多连边形成图，独立是传递的，所以 $\bar{G}$ 是多样的。

现在连边的两个点之间的选择是互不干涉的。

考虑一个特殊的情况——两层的菊花图。有一个非常简单的构造。

假设菊花图的根为 $u$，所有叶子依次为 $v_1,v_2,...,v_x$。

对于 $a$ 序列，$a_u=l,a_{v_1}=l+1,...,a_{v_{x-1}}=l+x-1,a_{v_x}=l+x$。

对于 $b$ 序列，$b_u=l+1,b_{v_1}=l+2,...,b_{v_{x-1}}=l+x,b_{x_v}=l$。

用同样的数字区间 $[l,l+x]$ 填写了 $a,b$ 同样的点集，且打了个等差 $1$。

这样子，内部反正是没有限制，不用管数字间的大小，也没有产生多余的 $a_i=b_i$ 情况数。

而与外部部分，因为都是用的连续段数字，相对关系也是满足的。

例如有个点 $t$ 与内部点有相对大小关系的限制，内部用的是 $[l,l+x]$ ，$t$ 所在点无论是 $[l^{\prime },l)/(l+x,r^{\prime }]$，$a,b$ 都是一致的。要么都小于最小值，要么都大于最大值。

将 $\bar{G}$ 中一些边断掉是不会出错的（因为这反而相当于外加了一些限制）。

所以，我们可以就将 $\bar{G}$ 直接断成若干个两层菊花图。

换言之，最后的答案最少个数可以通过调整构造变成最开始确定的点的数量。

有很多种裂成不同菊花图的方法，下面是官方做法：

枚举未分配的节点 $u$。

• 如果 $u$ 有临边点 $v$ 未分配，将 $u$ 和所有未分配的 $v$ 一起构成一个新的菊花图，并以 $u$ 为根。

• 否则，说明 $u$ 的所有邻居均已有过分配的菊花图。随便选一个邻居 $v$。

  • 如果 $v$ 所在的菊花图至少有 $3$ 个点，那么就可以把 $v$ 割裂出来，使得 $u,v$ 成为新的菊花图。

    注意：$v$ 此时不可能是其所在菊花图的根，如果是那么 $u$ 早就隶属与 $v$ 为根的那个菊花图了。

  • 否则，说明 $v$ 所在的菊花图只有两个点，将 $u$ 加入那个菊花图，并将那个菊花图转变为以 $v$ 为根即可。

$\bar{G}$ 中可存在的边很多，$n^2$ 级别的，但不一定是全都必须出现的。怎么快速求出想要的生成树？

用两个 set 维护已出现在 $\bar{G}$ 中的点和还未出现的点，在 dfs-tree 的时候顺便加边构出生成树的边。

时间复杂度：$O((n+m)\log n)$。

code

#include <bits/stdc++.h>
using namespace std;
#define maxn 500005
set < pair < int, int > > graph;
set < int > id, G[maxn], R[maxn];
int id1[maxn], id2[maxn], deg[maxn];

void dfs( int u ) {
    id.erase( u );
    int v = 0;
    while( 1 ) {
        auto it = id.upper_bound( v );
        if( it == id.end() ) break;
        v = *it;
        if( G[u].find( v ) != G[u].end() ) continue;
        R[u].insert( v );
        R[v].insert( u );
        dfs( v );
    }
}

int main() {
    int T, n, m;
    scanf( "%d", &T );
    while( T -- ) {
        scanf( "%d %d", &n, &m );
        for( int i = 1;i <= n;i ++ ) G[i].clear(), R[i].clear();
        id.clear(); for( int i = 1;i <= n;i ++ ) id.insert( i );
        for( int i = 1, u, v;i <= m;i ++ ) {
            scanf( "%d %d", &u, &v );
            G[u].insert( v );
            G[v].insert( u );
        }
        while( id.size() ) dfs( * id.begin() );
        int num = n;
        for( int i = 1;i <= n;i ++ ) {
            deg[i] = R[i].size();
            if( deg[i] ) graph.insert( make_pair( deg[i], i ) );
            else id1[i] = id2[i] = num --;
        }
        int l = 0, r = 0, u;
        while( graph.size() ) {
            u = graph.begin() -> second;
            u = *R[u].begin();
            graph.erase( make_pair( deg[u], u ) );
            vector < int > scc;
            for( int v : R[u] ) {
                graph.erase( make_pair( deg[v], v ) );
                if( deg[v] == 1 ) scc.push_back( v );
                else graph.insert( make_pair( -- deg[v], v ) ), R[v].erase( u );
            }
            id1[u] = ++ l; for( int i : scc ) id1[i] = ++ l, id2[i] = ++ r; id2[u] = ++ r;
        }
        for( int i = 1;i <= n;i ++ ) printf( "%d ", id1[i] ); puts("");
        for( int i = 1;i <= n;i ++ ) printf( "%d ", id2[i] ); puts("");
    }
    return 0;
}
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