[Arc079F] Namori Grundy
题目大意：
一个有向弱联通环套树。
一个点的sg值等于出边连向点的sg值的mex。
试问是否有办法给每个点分配sg值？
试题分析
题目大意把一些难点跳过了？？！
既然是sg值，那么考虑只有一个环的情况。
也就是说这个环必须由0、1构成，并且相邻两个不同，所以是二分图染色。。
那么显然奇环不行而偶环可以。
发现基环外向树上的那些树我们可以的sg值我们可以直接搞出来，那么我们现在可以获得环上每一个点的sg值的下界，下面就是进行调整了。
当所有点下界相同时，显然就是上面我们说过的情况。
不同我们就分情况讨论：
- \(a_{i-1}<a_{i}\) 不需要调整
- \(a_{i-1}=a_{i}\)调整为+1
- \(a_{i-1}>a_{i}\)依旧不需要调整。
这个过程能否停住是我们判断的标准。
显然若干次以后一定可以停住。
那么不合法的情况显然只有一种：奇环+下界相同。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
//#include<ctime>
//#include<cmath>
//#include<queue>
using namespace std;
#define LL long long
inline int read(){
int x=0,f=1; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int INF = 2147483600;
const int MAXN = 400010;
int N; int f[MAXN+1];
bool vis[MAXN+1]; int cir[MAXN+1],sta[MAXN+1];
int topx,top; int Next[MAXN<<1],Node[MAXN<<1],Root[MAXN<<1],cnt;
inline void insert(int u,int v){
Node[++cnt]=v; Next[cnt]=Root[u]; Root[u]=cnt; return;
} bool flag=false;
inline void Get_Cir(int k){
if(flag) return ; cir[++topx]=k; vis[k]=true;
for(LL x=Root[k];x;x=Next[x]){
LL v=Node[x]; if(flag) return ;
if(vis[v]){
for(LL j=topx;j>=1&&cir[j]!=v;j--) sta[++top]=cir[j];
sta[++top]=v; flag=true; return ;
} else Get_Cir(v);
} --topx; vis[k]=0; return ;
}
vector<int> vec[MAXN+1];
inline int Get_slope(int k){
vec[k].push_back(-1);
for(int x=Root[k];x;x=Next[x]){
int v=Node[x]; if(vis[v]) continue;
vec[k].push_back(Get_slope(v));
} sort(vec[k].begin(),vec[k].end()); vec[k].push_back(INF);
for(int i=0;i<vec[k].size();i++){
if(vec[k][i]+1!=vec[k][i+1]){
return vec[k][i]+1;
}
}
}
int col[MAXN+1];
inline bool state(){
for(int i=1;i<=top;i++) if(col[i]!=col[1]) return false;
return true;
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
N=read(); int x=N;
for(int i=1;i<=N;i++) f[i]=read(),insert(f[i],i);
for(int i=1;i<=N&&!flag;i++) Get_Cir(i); memset(vis,false,sizeof(vis));
if(!(top&1)){puts("POSSIBLE"); return 0;}
for(int i=1;i<=top;i++) vis[sta[i]]=1;
for(int i=1;i<=top;i++) col[i]=Get_slope(sta[i]);
puts(((top&1)&&state())?"IMPOSSIBLE":"POSSIBLE");
return 0;
}