思路与算法

给每条边编号。片段中相邻两条边必须直接接续，分别记录每条边唯一被要求的后继和前驱。遇到不存在的边，或同一边被要求不同后继/前驱，立即判不可能。强制接续关系若形成环，无法写成不跨首尾的线性片段路线，判不可能；其余形成若干链，把每条链压为起点到终点的一条边。压缩图要求每个点入度等于出度，所有有边的点在同一弱连通分量，且1号点有压缩边经过。满足则存在从1出发的Euler回路。

正确性说明

任意满足片段的线性路线必须保持所有指定边接续，所以冲突不可能解决，强制环也没有可以放置路线首尾的断口。无环时每条强制链必须完整连续出现；把它压成边不丢失其他自由接续。原路线于是与压缩图从1出发的Euler回路一一对应。有限有向图所有非孤立点弱连通且各点出入度相等，足以且必须存在Euler回路。将其压缩边展开即可满足每条片段，因此判定正确。

复杂度

设L为全部片段长度之和。边查找用哈希表，期望O(N+M+L)时间；并查集弱连通检查O((N+M)α(N))，初始化O(N+M)。空间O(N+M)，片段可流式处理。哈希键使用精确有序点对，哈希碰撞由容器比较键处理，不影响答案。

易错点

本题明确片段不能跨完整路线末尾再接开头。重复片段和重叠片段不应重复占边，但要求同一边出现两次会成环或冲突，应拒绝。普通图的Euler条件不够，必须先压强制链；1号在某链内部不代表能在那里切断该链。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DSU {
    vector<int> p;
    DSU(int n) : p(n) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        return p[x] == x ? x : p[x] = find(p[x]);
    }
    void join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b)
            p[a] = b;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m))
        return 0;
    vector<int> u(m), v(m), nx(m, -1), pr(m, -1), in(n), out(n);
    unordered_map<long long, int> id;
    id.reserve(m * 2);
    DSU d(n);
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i];
        --u[i];
        --v[i];
        id[1LL * u[i] * n + v[i]] = i;
        d.join(u[i], v[i]);
        in[v[i]]++;
        out[u[i]]++;
    }
    bool ok = true;
    for (int i = 0; i < n; i++)
        if (in[i] != out[i] || ((in[i] + out[i]) && d.find(i) != d.find(0)))
            ok = false;
    int t;
    cin >> t;
    while (t--) {
        int k, last = -1, a;
        cin >> k >> a;
        --a;
        for (int j = 1, b; j < k; j++) {
            cin >> b;
            --b;
            auto it = id.find(1LL * a * n + b);
            int e = it == id.end() ? -1 : it->second;
            if (e < 0)
                ok = false;
            if (last >= 0 && e >= 0) {
                if (nx[last] >= 0 && nx[last] != e)
                    ok = false;
                if (pr[e] >= 0 && pr[e] != last)
                    ok = false;
                nx[last] = e;
                pr[e] = last;
            }
            last = e;
            a = b;
        }
    }
    vector<int> seen(m), ci(n), co(n);
    DSU compressed(n);
    int chains = 0;
    for (int i = 0; i < m; i++)
        if (pr[i] < 0) {
            chains++;
            int e = i;
            while (e >= 0 && !seen[e]) {
                seen[e] = 1;
                if (nx[e] < 0)
                    break;
                e = nx[e];
            }
            co[u[i]]++;
            ci[v[e]]++;
            compressed.join(u[i], v[e]);
        }
    for (int i = 0; i < m; i++)
        if (!seen[i])
            ok = false;
    for (int i = 0; i < n; i++)
        if (ci[i] != co[i] || ((ci[i] + co[i]) && compressed.find(i) != compressed.find(0)))
            ok = false;
    if (!chains || !co[0])
        ok = false;
    cout << (ok ? "TAK\n" : "NIE\n");
}