思维懒惰, 人云亦云的用高级数据结构是不好的习惯

懵逼的 题目

传送至 Bilibili

扯淡的 题解

最近太颓了啥题也没写所以没写什么blog…正好做这题来着…就写一下好了…

因为要删边, 显然离线, 然后考虑一下这个只少有两条路径Emmmmm这不是联通块嘛!
于是问题就变成了: 在一个不断加边的图中, 询问两个点是否在一个联通块里

大体思路就是先删边, 之后跑一遍Tarjan, 把联通块缩一下, 然后加边的时候判断当前的两个点from, to是否联通, 如果联通, 把这两个点之间的路径一起缩成一个点, 否则用并查集记录这两个点联通

在并查集里缩两个点之间的路径显然是要找到LCA然后把整个路径上的点都union一下, 然后就遇到一(hen)些(duo)问题, 怎么在一个并查集里找LCA? 我们不能路径压缩, 这还好办, 因为一个点只能被缩点一次, 那么怎么在一个不断变化的并查集里找LCA…因为会缩点, 所以一个点的深度是会变化的, 所以我们只好先把整个树建出来, 然后确定好deep, 缩点的时候置新节点的deep为整条链上最小的deep, 每个节点只会收缩一次, 所以复杂度$n \lg n$

沙茶的 代码

具体实现我拿了一个并查集(blfa)代表他所属的被缩的点的编号, 一个并查集(ltfa)代表两个已经缩好的点是否联通, tfa, tb, tg都是维护并查集的那棵树的, gg, gb是存图的…硬生生的把100 line的代码改到了200 line+

/**************************************************************
    Problem: 3069
    User: Cansult
    Language: C++
    Result: Accepted
    Time:4176 ms
    Memory:23976 kb
****************************************************************/

// 搞一下联通块, 如果两个点不在一个块上的话, 那么中间一定没有第二条路?
// 加边的时候...怎么搞嘞...直接看两个块是不是联通? 如果联通就合并块 不联通就记为联通?
// 维护边...再搞个并查集好了  
// emmmmmm好麻烦啊...
// 好麻烦啊...
// 好麻烦啊...
// 好麻烦啊...
// 好麻烦啊...
// 好麻烦啊...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <set>
#define MAXN (100000 + 5)
#define rev(i) ((((i) - 1) ^ 1) + 1)
#define pii pair<int, int>
using namespace std;
const char __ok[5] = "TAK", ___ok[5] = "NIE";
struct edg
{
    int from, to, next;
} gb[MAXN << 1], tb[MAXN << 1];
struct que
{
    int from, to;
    bool isDel;
} q[MAXN];
pii ade[MAXN];
int gg[MAXN], cntg, tg[MAXN], cntt, n, m, blfa[MAXN], cntdfn, dfn[MAXN], low[MAXN], qn, tfa[MAXN], deep[MAXN], ltfa[MAXN];
char ans[MAXN][5];
set<int> he[MAXN];
multiset<pii> isdel;
stack<int> s;
void adn(edg* b, int* g, int& cntb, int from, int to)
{
    b[++cntb].next = g[from];
    b[cntb].from = from, b[cntb].to = to;
    g[from] = cntb;
}
int find(int* fa, int x)
{ return (fa[x] == x ? x : (fa[x] = find(fa, fa[x]))); } 
void uni(int* fa, int son, int father)
{ fa[find(fa, son)] = find(fa, father); }
int cfa(int x, int y)
{
    if (x == y)
        return x;
    if (deep[x] < deep[y])
        swap(x, y);
    int fa = cfa(find(blfa, tfa[x]), y);
    uni(blfa, x, fa);
    uni(blfa, y, fa);
    return fa;
}
void dfs(int dq, int de)
{
    deep[dq] = de;
    for (int i = tg[dq]; i; i = tb[i].next)
    {
        if (tb[i].to != tfa[dq])
            tfa[tb[i].to] = dq, dfs(tb[i].to, de + 1);
    }
}
void tarjan(int* g, edg* b, int dq, int fedg)
{
    dfn[dq] = low[dq] = ++cntdfn;
    s.push(dq);
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (!dfn[b[i].to])
        {
            tarjan(g, b, b[i].to, i);
            low[dq] = min(low[dq], low[b[i].to]);
            if (low[b[i].to] == dfn[b[i].to])
                he[dq].insert(b[i].to);
        }
        else if (rev(i) != fedg)
            low[dq] = min(low[dq], dfn[b[i].to]);
    }
    if (low[dq] > dfn[b[fedg].from] || !b[fedg].from)
    {
        while (!s.empty() && s.top() != dq)
        {
            blfa[s.top()] = dq;
            s.pop();
        }
        s.pop();
    }
}
void init()
{
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(gg, gb, i, 0);
    for (int i = 1; i <= n; i++)
    {
        int fx = find(blfa, i);
        for (set<int>::iterator j = he[i].begin(); j != he[i].end(); j++)
        {
            int fy = find(blfa, *j);
            if (find(ltfa, fx) != find(ltfa, fy))
            {
                uni(ltfa, fx, fy);
                adn(tb, tg, cntt, fx, fy);
                adn(tb, tg, cntt, fy, fx);
            }
        }
    }
    int infa[MAXN];
    for (int i = 1; i <= n; i++)
        infa[i] = ltfa[i];
    for (int i = qn; i >= 1; i--)
    {
        if (q[i].isDel)
        {
            int fx = find(blfa, q[i].from), fy = find(blfa, q[i].to);
            if (find(infa, fx) != find(infa, fy))
            {
                adn(tb, tg, cntt, fx, fy);
                adn(tb, tg, cntt, fy, fx);
                uni(infa, fx, fy);
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        int dq = find(blfa, i);
        if (!deep[dq])
            tfa[dq] = dq, dfs(dq, 1);
    }
}
void solve()
{   
    for (int i = qn; i; i--)
    {
        int fx = find(blfa, q[i].from), fy = find(blfa, q[i].to);
        if (q[i].isDel)
        {
            if (find(blfa, find(ltfa, fx)) == find(blfa, find(ltfa, fy)))
                cfa(fy, fx);
            else
                uni(ltfa, fx, fy);
        }
        else
            strcpy(ans[i], fx == fy ? __ok : ___ok);
    }
}
int main()
{

    scanf("%d%d%d", &n, &m, &qn);
    for (int i = 1; i <= n; i++)
        blfa[i] = i, ltfa[i] = i;
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &ade[i].first, &ade[i].second);
    for (int i = 1; i <= qn; i++)
    {
        char sre;
        getchar();
        scanf("%c%d%d", &sre, &q[i].from, &q[i].to);
        q[i].isDel = (sre == 'Z');
        if (q[i].isDel)
        {
            isdel.insert(make_pair(q[i].from, q[i].to));
            isdel.insert(make_pair(q[i].to, q[i].from));
        }
    }
    for (int i = 1; i <= m; i++)
    {
        if (isdel.find(ade[i]) == isdel.end())
        {
            adn(gb, gg, cntg, ade[i].first, ade[i].second);
            adn(gb, gg, cntg, ade[i].second, ade[i].first);
        }
        else
            isdel.erase(ade[i]);
    }
    init();
    solve();
    for (int i = 1; i <= qn; i++)
        if (!q[i].isDel)
            printf("%s\n", ans[i]);
    return 0;
}

/*
7 8 7
1 2
1 3
1 4
2 3
3 4
3 7
7 4
5 6
Z 1 4
P 1 3
P 2 4
Z 1 3
P 1 3
Z 6 5
P 5 6
*/

好像全网就我和NeitherNor大爷写的非LCT…虽然NeitherNor大爷说那是并查集我怎么看不懂啊

By 不会LCT的 Cansult