Bracelet Crossings

此题复杂度没有挑战（ $N=50$ ），但是细节比较多。

检查一个方案合法性，有以下规则：

每种color必须连续出现，不能有中断，可以扫描一遍检测。
有包含关系的颜色，需要是一个堆栈顺序（不能是 $1 2 1 2$ 这样交错），用堆栈模拟就可以检测。
每种被包含颜色的父亲颜色必须是一致的。
没有包含关系的颜色之间的顺序要一致，这个可以把相邻颜色的顺序用一张图来表示，然后在上面跑DFS检查有没有环。
- 这里的重要条件是每个颜色在每条线上出现 $0$ 或 $2$ 次，所以不存在凹陷的形状，也就不会出现两种并列的颜色交换顺序的情况。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int T, n, m;  // <= 50
vector<int> c[55];
pi range[55];    // range for each color
int level[55];   // nested level of each color
int fa[55];      // nested father of each color
set<int> adj[55];
int vis[55];     // 1: on active path, 2: visited but no on active path
bool ok;
 
void dfs(int s) {
    if (vis[s] == 1)
        ok = false;     // there's circle
    if (vis[s]) return;
    vis[s] = 1;
    for (int u: adj[s]) {
        dfs(u);
    }
    vis[s] = 2;
};
 
int main() {
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        scanf("%d %d", &n, &m);
        fill(range, range+n, make_pair(-1,-1));
        for (int i = 0; i < m; i++) {
            int cnt;
            scanf("%d", &cnt);
            c[i].resize(cnt);
            for (int j = 0; j < cnt; j++) {
                int cl;
                scanf("%d", &cl);
                cl--;
                c[i][j] = cl;
                if (range[cl].first == -1) range[cl].first = i;
                range[cl].second = max(range[cl].second, i);
            }
        }
        // 保证颜色连续出现
        ok = true;
        for (int i = 0; i < m; i++) {
            bool cls[55];
            fill(cls, cls+n, false);
            for (int cl: c[i])
                cls[cl] = true;
            for (int j = 0; j < n; j++)
                if (!cls[j] && i >= range[j].first && i <= range[j].second)
                    ok = false; 
        }
        // 检查包含关系
        for (int i = 0; i < n; i++)
            adj[i].clear();
        fill(level, level+n, 0);
        fill(fa, fa+n, -1);
        for (int i = 0; i < m; i++) {
            stack<int> cls;
            for (int j = 0; j < c[i].size(); j++) {
                int cl = c[i][j];
                if (cls.empty() || cl != cls.top()) {
                    int f = cls.size() ? cls.top() : -1;
                    cls.push(cl);
                    if (level[cl] == 0) {
                        level[cl] = cls.size();
                        fa[cl] = f;
                    } else if (level[cl] != cls.size() || fa[cl] != f)
                        ok = false;
                    if (j)
                        adj[cl].insert(c[i][j-1]);
                } else
                    cls.pop();
            }
            if (cls.size()) ok = false;
        }
        // 检查顺序
        fill(vis, vis+n, false);
        for (int i = 0; i < n; i++)
            if (!vis[i])
                dfs(i);
        printf("%s\n", ok ? "YES" : "NO");
    }
    return 0;
}