给定n个点的竞赛图，给出一个方案把n个点分为A，B，C三个非空集合，使得所有的边要么连接着相同集合的点，要么从A指向B，要么从B指向C，要么从C指向A。
考虑钦定点 1 属于 B 集合，考察 1 的所有边。以 1 为起点的边，其终点必然属于 B 或 C 中的一个；同理，以 1 为终点的边，其起点必然属于 B 或 A 中的一个。并且，竞赛图保证了所有点都与 1 有边，即上述讨论可以覆盖到所有点。那么除 1 外的每个点都有两种选择，可以转化为 2-SAT 问题求解，简单分析可以知道每一条与 1 无关的边都可以转换为 2-SAT 上的一个限制。时间为 \(O(n^2)\)。
换个思路，其实竞赛图+非空集合这两个限制叠加在一起是非常紧的。我们可以通过考察三个点的两两关系证明如果存在方案，那么方案在轮换等价的意义上是唯一的。
依然考虑钦定 1 属于 B，并假设存在一个合法方案。想要构造一个新方案，不失一般性，假设至少有一个原本属于 C 的点变得不再属于 C。任意选取集合 A 中的一个点 a，集合 C 中的一个点 c，则一定有 \(a\to 1\)，\(1\to c\) 和 \(c\to a\)。如果 c 在新方案中不再属于 C，因为有 \(1\to c\)，那么它只能属于 B，由于存在 \(c\to a\)，那么 a 也必须改为属于 B。由于 a 的任意性，原 A 集合内的所有点都必须改为 B。类似的，现在 a 被改为了 B，那么集合 C 中的所有点也必须改为 B。也就是说，要想这个新方案合法，原 B 集合必须有一些点改为 A 和 C，但这也是不可能的。因为现在 a 和 c 都属于了 B，如果有另一个属于 B 的 b（要求 |B|>1） 变成了属于 A，则不符合 \(a\to b\)，同理这个 b 也不能属于 C。综上，要构造一个新方案，至少有一个原本属于 A 或 C 的点会变为属于 B，进一步会推出 A 和 C 集合必须为空，故不存在合法新方案。
于是可以钦定 \(1\in B\)，枚举 \(x\in A\)，\(y\in C\) 满足是一个三元环，然后将剩下的点一个个加入进去。如果存在一个合法方案且这个方案中 \(1\in B\)，\(x\in A\)，\(y\in C\)，那么其所有顶点包含 1，x 和 y 的子图也都存在合法方案且唯一，所以每次加入也最多有一种合法方式，一旦无法放入，说明最终的合法方案中 \((x,1,y)\) 不是分属于 A B C，而是同属于 B。那么就换一对 \((x,y)\) 重复上述步骤。这样做复杂度是 \(O(n^4)\)。
为了找到正确的三元组 \((x,1,y)\)，在没有合法方案的最坏情况下需要枚举所有 \((x,y)\)，这一步花了太多时间。我们考虑优化这一点。假设我们找到了第一个 \((x,1,y)\)，此时如果存在合法方案并且 \((x,1,y)\) 在方案中并非分属于 A B C（即同属于 B），那么说明存在一个 \((x',y')\)，使得 \(1,x,y\in B\)， \(x'\in A\)，\(y'\in C\) 。所以我们不断地去找有没有可以把之前枚举的所有点放在 B 里的新的 \(x'\) 和 \(y'\)，一旦找不到了，就说明在存在合法方案的情况下，最后枚举到的 \(x'\) 和 \(y'\) 一定就在方案中分别属于 A 和 C，而之前枚举的所有点包括 1 都属于 B，然后再一个个把剩下的点加入即可，复杂度可以做到 \(O(n^2)\)。
题解里写到用 random-shuffle 做到 n 方，不过没怎么搞清楚题解的意思。
这里给出第二种做法的代码
#include<bits/stdc++.h>
using ll=long long;
using namespace std;
void solve();
int main(){int t=1;// cin>>t;while(t--)solve();return 0;
}const int N=503;
int a[N][N];
int st[N];
void solve(){int n;cin>>n;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){cin>>a[i][j];a[j][i]=a[i][j]^1;}for(int i=2;i<=n;i++){if(a[i][1])st[i]=1;else st[i]=2;}auto add=[&](int u){st[u]=0;for(int i=1;i<=n;i++)if(st[i]){if(st[i]==1&&a[u][i])st[i]=3;if(st[i]==2&&a[i][u])st[i]=3;}};int x=-1,y=-1; // x->1->yfor(int i=2;i<=n;i++)if(st[i]==1){for(int j=2;j<=n;j++){if(a[j][i]&&st[j]==2){add(i);add(j);x=i;y=j;break;}}}if(x==-1){cout<<"0 0 0\n";return;}st[x]=-1;//Ast[y]=-2;//Cvector<int>A,B,C;A.push_back(x);C.push_back(y);for(int i=1;i<=n;i++)if(st[i]==0)B.push_back(i);for(int i=1;i<=n;i++){if(st[i]>0){int wb=a[i][1],wa=a[i][x],wc=a[i][y];for(auto j:A)if(wa!=-1&&(wa^a[i][j])){wa=-1;break;}for(auto j:B)if(wb!=-1&&(wb^a[i][j])){wb=-1;break;}for(auto j:C)if(wc!=-1&&(wc^a[i][j])){wc=-1;break;}if(wb==1&&wc==0)A.push_back(i);else if(wc==1&&wa==0)B.push_back(i);else if(wa==1&&wb==0)C.push_back(i);else{// cerr<<"!\n";cout<<"0 0 0\n";return;}}}cout<<A.size()<<" "<<B.size()<<" "<<C.size()<<endl;for(auto j:A)cout<<j<<" ";cout<<endl;for(auto j:B)cout<<j<<" ";cout<<endl;for(auto j:C)cout<<j<<" ";cout<<endl;
}
