python/TangDou/AcWing/DCC/P4214.cpp

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3010, M = N << 4;

const LL mod = 19491001;
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int n, m;

// 最简并查集
int p[N];
int find(int x) {
    if (x == p[x]) return x;
    return p[x] = find(p[x]);
}

LL f[N];

int dfn[N], low[N], ts;
int stk[N], top;
int bcnt;

/*
// 边双模板
vector<int> bcc[N];
int dcc[N];
void tarjan(int u, int from) {
    dfn[u] = low[u] = ++ts;
    stk[++top] = u;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
        } else if (i != (from ^ 1))
            low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u]) {
        ++bcnt;
        int x;
        do {
            x = stk[top--];
            bcc[bcnt].push_back(x); // 记录边双中有哪些点
            dcc[x] = bcnt;          // 反向记录x这个点在bcnt这个边双里面
        } while (x != u);
    }
}
*/
int dcc[N]; // 记录每一个节点在哪个边双中
bool vis[M << 1];
void tarjan(int u, int fa) {
    low[u] = dfn[u] = ++ts;
    stk[++top] = u;

    for (int i = h[u]; ~i; i = ne[i]) {
        if (vis[i]) continue;
        if ((i == fa) || ((i ^ 1) == fa)) continue;
        int v = e[i];

        if (!dfn[v]) {
            vis[i] = vis[i ^ 1] = 1;
            tarjan(v, fa);
            vis[i] = vis[i ^ 1] = 0;
            low[u] = min(low[u], low[v]);
        } else
            low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        dcc[u] = ++bcnt;
        while (stk[top] != u)
            dcc[stk[top--]] = bcnt;
        top--;
    }
}

int calc(int u, int v) {
    int x = find(u), y = find(v);
    if (x != y) return 0;
    if (dcc[u] != dcc[v]) return 1;
    if (f[u] == f[v]) return 3;
    return 2;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("P4214.in", "r", stdin);
#endif
    memset(h, -1, sizeof h);
    scanf("%d %d", &n, &m);                // 节点数和管道数
    for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集

    for (int i = 1; i <= m; i++) { // 枚举每条边
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b), add(b, a);

        // 并查集这是在干什么？记录点与点的连通性？
        int x = find(a), y = find(b);
        if (x != y) p[x] = y;
    }

    // base case初始化
    for (int i = 1; i <= n; i++) f[i] = 1ll;

    // 为什么是m+1次呢？
    for (int x = 1; x <= m + 1; x++) {
        // tarjan初始化
        memset(low, 0, sizeof low);
        memset(dfn, 0, sizeof dfn);
        ts = 0, bcnt = 0, top = 0;
        // 跑Tarjan,可能不连通
        for (int i = 1; i <= n; i++)
            if (!dfn[i]) tarjan(i, x << 1);

        for (int i = 1; i <= n; i++)
            f[i] = f[i] * mod + (LL)dcc[i];
    }

    // 根据题意，计算最终的结果
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            ans += calc(i, j);
    // 输出
    printf("%d\n", ans);
    return 0;
}