题解：P11606 [PA 2016] 构树 / Reorganizacja

· · 题解

很好的一道构造题。
看到题目让我们构造一棵树，首先就应该考虑怎么选根：

选不到直接 NIE。
接下来考虑如何往下构造，似乎并没有什么新的性质，那就直接推广选根的操作，把其他一坨节点全挂在根下面。考虑确定了根影响了什么，也就是如果某一节点的祖先一定是根，这个关系就没用了。删掉这些关系，重复选根的操作，注意我们有根了所以以后只需要建森林即可：

显然建不出森林了也要 NIE。
代码如下，一些细节见注释：

#include<bits/stdc++.h>
//#define int long long
#define db double
#define maxn 3000005
#define mod 998244353
#define fir first
#define sec second
#define pr pair<int,int>
#define pb push_back
#define mk make_pair
#define inf 10000000000000000
using namespace std;
inline int read()
{
    int SS=0,WW=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')WW=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        SS=(SS<<1)+(SS<<3)+(ch^48);
        ch=getchar();
    }
    return SS*WW;
}
inline void write(int XX)
{
    if(XX<0)putchar('-'),XX=-XX;
    if(XX>9)write(XX/10);
    putchar(XX%10+'0');
}
struct con
{
    int x,y;char c;
}e[maxn];
int n,m,rt,fa[maxn],pa[maxn],q[maxn];
bool no[maxn];
int find(int f)
{
    return q[f]==f?f:q[f]=find(q[f]);
}
signed main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)e[i].x=read(),e[i].y=read(),cin>>e[i].c,e[i].c=='T'?no[e[i].x]=1:no[e[i].y]=1;
    for(int i=1;i<=n;i++)if(!no[i])rt=i;//整棵树的根
    if(!rt)puts("NIE"),exit(0);
    for(int i=1;i<=n;i++)pa[i]=rt,fa[i]=-1;//全挂在根下面，注意fa=0是有意义的要初始化为-1
    fa[rt]=0;
    for(int T=1;T<n;T++)
    {
        for(int i=1;i<=n;i++)q[i]=i,no[i]=(fa[i]==-1?0:1);//在剩余节点中建树
        for(int i=1;i<=m;i++)
            if(fa[e[i].y]==-1&&e[i].c=='T')
            {
                no[e[i].x]=1;//不能为后代
                if(fa[e[i].x]==-1)q[find(e[i].x)]=find(e[i].y);//并查集维护祖先关系
            }
        for(int i=1;i<=m;i++)
            if(e[i].c=='N'&&find(e[i].x)==find(e[i].y))no[e[i].y]=1;//y不能既为x祖先又不能为x祖先
        rt=0;
        for(int i=1;i<=n;i++)if(!no[i])rt=i;//找森林中的某棵树的根
        if(!rt)puts("NIE"),exit(0);//找不到了
        fa[rt]=pa[rt];//与挂上的那个节点确认父子关系
        for(int i=1;i<=n;i++)if(find(i)==find(rt))pa[i]=rt;//与这个根有祖先关系就挂在这个根下面
    }
    for(int i=1;i<=n;i++)write(fa[i]),puts("");
    return 0;
}