P3443 [POI2006]LIS-The Postman

Alex_Wei · 2021-12-19 22:29:41 · 题解

*P3443 [POI2006]LIS-The Postman

POI 合集。

每条路径片段的限制形如在片段中出现的相邻两条边必须先后走，因为一条边有向边仅出现一次。

所有限制形成一条边先后走的关系的链（有点像 CSP2019 T4 树上的数），将这条链缩成从起点到终点的一条边，然后跑欧拉回路即可，最后输出这条边时要再展开成链，因此要记录每条链上的结点顺序。

若限制关系出现环或分叉则无解，这可以通过并查集或链表维护。时间复杂度线性对数或线性。

const int N = 5e5 + 5;
int n, m, q, node, cur[N], fa[N];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
int u[N], v[N], in[N], deg[N];
int vis[N], vert, top, stc[N];
vpii e[N], E[N];
vint G[N], pa[N];
gp_hash_table <ll, int> mp, buc;
ll hsh(int a, int b) {return 1ll * a * N + b;}

void dfs(int id) {
    if(!vis[id]) vert++, vis[id] = 1;
    for(int &i = cur[id]; i < E[id].size(); ) {
        pii it = E[id][i++]; dfs(it.fi);
        if(it.se > n) stc[++top] = it.se;
    } stc[++top] = id;
}

bool Med;
int main(){
    cin >> n >> m, node = m;
    for(int i = 1; i <= m; i++) {
        u[i] = read(), e[u[i]].pb(v[i] = read(), i);
        mp[hsh(u[i], v[i])] = fa[i] = i;
    } q = read();
    for(int i = 1; i <= q; i++) {
        static int p[N]; int k = read();
        for(int j = 1; j <= k; j++) p[j] = read();
        for(int j = 1; j + 1 < k; j++) {
            int u = mp[hsh(p[j], p[j + 1])], v = mp[hsh(p[j + 1], p[j + 2])];
            if(!u || !v) puts("NIE"), exit(0);
            if(buc.find(hsh(u, v)) != buc.end()) continue;
            if(G[u].size() || deg[v] || find(u) == find(v)) puts("NIE"), exit(0);
            buc[hsh(u, v)] = 1, G[u].pb(v), deg[v]++, fa[fa[u]] = fa[v];
        }
    } for(int i = 1; i <= m; i++)
        if(G[i].size() && !deg[i]) {
            int cur = u[i], p = i, x = ++node;
            while(1) {
                cur = v[p];
                if(!G[p].size()) break;
                else pa[x].pb(v[p]), p = G[p][0];
            } E[u[i]].pb(cur, x);
        }
    for(int i = 1; i <= n; i++) for(pii it : e[i])
        if(!G[it.se].size() && !deg[it.se]) E[i].pb(it);
    for(int i = 1; i <= n; i++) for(pii it : E[i]) in[it.fi]++;
    for(int i = 1; i <= n; i++)
        if(E[i].size() != in[i]) puts("NIE"), exit(0);
        else if(!E[i].size()) vert++;
    dfs(1);
    if(vert != n) puts("NIE"), exit(0);
    puts("TAK");
    while(top) {
        if(stc[top] > n) for(int it : pa[stc[top]]) cout << it << "\n";
        else cout << stc[top] << "\n"; top--;
    } return  0;
}