Description
一个有向弱联通环套树。 一个点的sg值等于出边连向点的\(sg\)值的\(mex\)。试问是否有办法给每个点分配\(sg\)值。
注：基环内向树
基环外向树
居然有水印！！！
Hint
\(2\leq N \leq 200000 \\ 1\leq p_i \leq N\quad p_i\neq i\)
Solution
首先，一棵树一定有解，且每个树上的节点的权值唯一确定。然后我们看题目，基环分两类：基环外向树，基环内向树。然而由于所有的点入度大于等于1，所以并没有内向树。
那么现在只剩下基环外向树，我们先把环断掉一条\((u,v)\ : \ u \to v\)，原图变成一颗外向树，计算树上节点的\(sg\)值，对于\(u\)来说，设当前外向树上\(u\)的\(sg\)值为\(tmp_1\)，\(u\)的儿子中没有出现的第二大的值为\(tmp_2\)（第一大的是\(tmp_1\)），那么\(sg_u \in \{tmp_1, tmp_2 \}\)。
1、\(sg_u \ = \ tmp_1\)：考虑连上边\((u,v)\)后的影响，那么只要满足$sg_v \not = tmp_1 $即可。
2、\(sg_u \ = \ tmp_2\)：这时\(，sg_v \ = \ tmp_1 ， sg_u \ = \ tmp_2\)，那么只需从u开始往父亲跳，判断是否合法即可。
Code
/**************************************************************
Problem: 3177
User: ez_hjw
Language: C++
Result: Accepted
Time:111 ms
Memory:16148 kb
****************************************************************/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 200000 + 10;
int n, p[maxn], tim = 0, Sx, Tx, col[maxn], sg[maxn];
int cnt, h[maxn];
struct enode{
int v, n, op;
enode() {}
enode(int _v, int _n):v(_v), n(_n) { op = 0; }
}e[maxn << 1];
inline void addedge(int u, int v) {
cnt ++; e[cnt] = enode(v,h[u]); h[u] = cnt;
}
int vis[maxn << 1];
inline int get_sg(int u) {
for(int i = h[u];~ i;i = e[i].n) {
int v = e[i].v;
if(e[i].op) continue;
vis[sg[v]] = 1;
}
int tmp = -1;
for(int i = 0;;i ++) if(!vis[i]) {
tmp = i;
break;
}
for(int i = h[u];~ i;i = e[i].n) {
int v = e[i].v;
if(e[i].op) continue;
vis[sg[v]] = 0;
}
return tmp;
}
void dfs(int u) {
col[u] = tim;
for(int i = h[u];~ i;i = e[i].n) {
int v = e[i].v;
if(e[i].op) continue;
if(col[v]) {
if(col[v] == tim) {
Sx = u; Tx = v;
e[i].op = 1;
}
}
else dfs(v);
}
sg[u] = get_sg(u);
}
int main() {
scanf("%d", &n); cnt = 0;
memset(h,-1,sizeof(h));
for(int i = 1;i <= n;i ++) {
scanf("%d", &p[i]);
addedge(p[i],i);
}
for(int i = 1;i <= n;i ++) {
if(!col[i]) {
tim ++;
dfs(i);
}
}
int tmp1 = get_sg(Sx);
vis[tmp1] = 1;
int tmp2 = get_sg(Sx);
vis[tmp1] = 0;
if(sg[Tx] != tmp1) {
puts("POSSIBLE");
return 0;
}
sg[Sx] = tmp2;
int u = Sx;
while(u != Tx) {
u = p[u];
sg[u] = get_sg(u);
}
sg[Tx] = get_sg(Tx);
if(sg[Tx] != tmp1) puts("IMPOSSIBLE");
else puts("POSSIBLE");
return 0;
}
转载于:https://www.cnblogs.com/ezhjw/p/9518523.html
相关资源：JAVA上百实例源码以及开源项目
