BZOJ 1123 tarjan

题目链接

题意：一张无向图，把第$i$个点关联的所有边去掉，求无向图中有多少个点对不连通。

题解：

如果割的不是割点，那么总答案是$2\times (n-1)$.

如果是割点，要分别考虑每个子树的贡献.

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 1e5 + , M = 5e5 + ;

int head[N], ver[M * ], Next[M * ];

int dfn[N], low[N], Size[N];

ll ans[N];

bool cut[N];

int n, m, tot, num; ///时间戳号

void add(int u, int v)

{

    ver[++tot] = v, Next[tot] = head[u], head[u] = tot;

}

void tarjan(int u)

{

    dfn[u] = low[u] = ++num; Size[u] = ;

    int flag = , sum = ;

    for(int i = head[u]; i; i = Next[i])

    {

        int v = ver[i];

        if(!dfn[v])

        {

            tarjan(v);

            Size[u] += Size[v];

            low[u] = min(low[u], low[v]);

            if(low[v] >= dfn[u])

            {

                flag++;

                ans[u] += (ll)Size[v] * (n - Size[v]);

                sum += Size[v];

                if(u !=  || flag > ) cut[u] = true;

            }

        }

        else low[u] = min(low[u], dfn[v]);

    }

    if(cut[u]) ans[u] += (ll)(n - sum - ) * (sum + ) + (n - );

    else ans[u] =  * (n - );

}

int main()

{

    scanf("%d %d", &n, &m); tot = ;

    for(int i = ; i <= m; i++)

    {

        int u, v; scanf("%d %d", &u, &v);

        if(u == v) continue;

        add(u, v), add(v, u);

    }

    tarjan();

    for(int i = ; i <= n; i++) printf("%lld\n", ans[i]);

    return ;

}

Code