题解：AT_joisc2019_k 合併 (Mergers)

题目传送门

前言

联考题，被初一的我切了。看到题解区里没有 Tarjan 做法，于是来补一篇 Tarjan 题解。

分析

因为相同州的城市不会分裂，所以可以给相同州的成市连边（注意不是两两连边，连成一个环就行），发现把国家分成两个部分就相当于断掉一条道路。那么如果整个国家就是一个边双连通分量，就不可能分裂。

于是我们可以先给图边双连通分量缩点，可以发现缩点后两个点中城市所属的州一定不相同。合并两个州的操作相当于在缩点后给两个点连边。然后就可以用经典的答案统计法了：设缩点后度数为 \(1\) 的节点有 \(s\) 个，则需要连的边数为 \(\lceil \frac{s}{2} \rceil\) 个。

代码

#include <bits/stdc++.h>
using namespace std;
#define N 1000010
int n, K, a[N], hd[N], ikun[N], nxt[N * 7], to[N * 7], tot = 1, fa[N], dep[N], dfn[N], low[N], pre[N], idx, c[N], sum, mkp[N], ans;
bool bri[N * 7], vis[N];
inline void add(int u, int v)
{
    tot++;
    nxt[tot] = hd[u];
    to[tot] = v;
    hd[u] = tot;
}
inline void tarjan(int x, int frm) // 跑 Tarjan，找割边
{
    dfn[x] = ++idx;
    low[x] = idx;
    for (int i = hd[x]; i; i = nxt[i])
    {
        int y = to[i];
        if (i == frm || (i ^ 1) == frm) // 注意重边！
        {
            continue;
        }
        if (!dfn[y])
        {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x])
            {
                bri[i] = 1;
                bri[i ^ 1] = 1;
            }
        }
        else
        {
            low[x] = min(low[x], dfn[y]);
        }
    }
}
inline void dfs(int x) // 找到割边后缩点
{
    c[x] = sum;
    for (int i = hd[x]; i; i = nxt[i])
    {
        if (bri[i] || bri[i ^ 1])
        {
            continue;
        }
        int y = to[i];
        if (!c[y])
        {
            dfs(y);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> K;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++) // 读入所属州并连边
    {
        cin >> a[i];
        ikun[a[i]] = i;
        if (pre[a[i]])
        {
            add(i, pre[a[i]]);
            add(pre[a[i]], i);
        }
        pre[a[i]] = i;
        fa[i] = i;
        dep[i] = 1;
    }
    for (int i = 1; i <= n; i++) // 要连成环
    {
        if (pre[i])
        {
            add(pre[i], ikun[i]);
            add(ikun[i], pre[i]);
        }
    }
    tarjan(1, 0);
    for (int i = 1; i <= n; i++)
    {
        if (!c[i])
        {
            sum++;
            dfs(i);
        }
    }
    if (sum == 1)
    {
        cout << 0;
        return 0;
    }
    ans = sum;
    for (int i = 1; i <= n; i++)
    {
        for (int j = hd[i]; j; j = nxt[j])
        {
            int k = to[j];
            if (c[i] != c[k])
            {
                if (mkp[c[i]] && (mkp[c[i]] != c[k])) // 判断点的度数是否为 1
                {
                    if (!vis[c[i]])
                    {
                        ans--;
                        vis[c[i]] = 1;
                    }
                }
                if (mkp[c[k]] && (mkp[c[k]] != c[i]))
                {
                    if (!vis[c[k]])
                    {
                        ans--;
                        vis[c[k]] = 1;
                    }
                }
                mkp[c[i]] = c[k];
                mkp[c[k]] = c[i];
            }
        }
    }
    cout << (ans + 1) / 2;
    return 0;
}