[??记录]AT2663 [ARC079D] Namori Grundy
command_block
2021-05-17 07:31:35
**题意** ： 给出一棵 $n$ 个点 $n$ 条边的基环外向树。
要为为每个点设置了一个权值，记 $a_i$ 表示点 $i$ 的权值。
要求 $a$ 图满足如下性质：
- $a_i\in {\rm N}$
- 对于每条边 $(i\rightarrow j)$，满足 $a_i≠a_j$
- 对于所有 $i,x(0\le x\lt a_i)$ ，存在一条边 $(i\rightarrow j)$ 满足 $x=a_j$
判定是否存在一种合法的权值填写方案。
$n\leq 2\times 10^5$ ，时限$\texttt{2s}$。
------------
先考虑一棵外向树如何分配权值。
不难发现，只需每次将 $a_u$ 设为 ${\rm mex}_{u\rightarrow v}a_v$ 即可满足条件。这也是唯一一种能满足条件的方案。
再考虑环。不难想到，若确定了环上的某个 $a_u$ ，则类似于树的情况，容易处理。
对于某个环上的 $u$ ，记其外向树儿子的 $a_v$ 集合为 $S$。
那么最终 $u$ 会等于 ${\rm mex}(S)$ 或者 ${\rm mex}\Big(S+\{{\rm mex}(S)\}\Big)$ ，做两次即可。
复杂度 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define MaxN 200500
using namespace std;
const int mod=1000000007;
int f[MaxN];
int find(int u)
{return f[u]==u ? u : f[u]=find(f[u]);}
bool merge(int u,int v){
u=find(u);v=find(v);
if (u==v)return 0;
f[u]=v;return 1;
}
vector<int> g[MaxN];
int fl,st[MaxN],tot;
void pfs(int u)
{
st[++tot]=u;
if (u==fl)return ;
for (int i=0;i<g[u].size();i++){
pfs(g[u][i]);
if (st[tot]==fl)return ;
}tot--;
}
bool o[MaxN],e[MaxN];int w[MaxN];
void dfs(int u)
{
for (int i=0;i<g[u].size();i++)
if (!e[g[u][i]])dfs(g[u][i]);
for (int i=0;i<=g[u].size();i++)o[i]=0;
for (int i=0;i<g[u].size();i++)o[w[g[u][i]]]=1;
w[u]=0;while(o[w[u]])w[u]++;
}
int n;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)f[i]=i;
int x0,y0;
for (int i=1,p;i<=n;i++){
scanf("%d",&p);
if (merge(i,p))g[p].pb(i);
else {x0=i;y0=p;}
}fl=y0;pfs(x0);
dfs(st[1]);
if (w[st[tot]]!=w[st[1]]){puts("POSSIBLE");return 0;}
int u=st[tot],sav=w[st[1]];
for (int i=0;i<=g[u].size()+1;i++)o[i]=0;
for (int i=0;i<g[u].size();i++)o[w[g[u][i]]]=1;
o[w[st[1]]]=1;while(o[w[u]])w[u]++;
e[u]=1;dfs(st[1]);
if (w[st[1]]==sav){puts("POSSIBLE");return 0;}
puts("IMPOSSIBLE");
return 0;
}
```