363. B城（Tarjan）

亦凉 2021-12-11 03:07 223阅读 0赞

题目链接：[https://mp.csdn.net/mdeditor\#][https_mp.csdn.net_mdeditor]

题意是要我们求把与节点 i 关联的所有边去掉以后（不去掉节点 i 本身），无向图有多少个有序点（x，y），满足 x 和 y 不连通。（注：有序点 所以 （x,y）和（y,x）是不同的）

看到这里自然想到割点。 回顾割点的性质和定义：割点是指把这个点和与之相连的边删除后，强联通图的数量将增加。

我们可以想，如果i不是割点，那么把点i关联的边去掉。一定只有2\*（n - 1）对点。  
如果点i是割点，那么把点i关联的边去掉。然后构成了多个强联通图。根据题意可知，应该将每个强联通子图的结点个数两两相乘在相加 同时还需要加上（n-1) 然后还要注意一点 剩下的可能还有一个强联通子图 也需要考虑。

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    int n,m;
    int Stack[100100],dfn[100100],low[100100],vis[100100],id[100100];
    int Size[100100];
    ll sum[100100];
    int top,col_num,cnt_num;
    vector<int> Q[100100];
    
    void Tarjan(int x)
    {
        dfn[x] = ++ cnt_num;
        low[x] = cnt_num;
        Stack[++ top] = x;
        vis[x] = 1;
        Size[x] = 1;
        int s = 0,flag = 0;
        for(int i = 0; i < Q[x].size(); i ++)
        {
            int v = Q[x][i];
            if(!dfn[v])
            {
                Tarjan(v);
                Size[x] += Size[v];
                low[x] = min(low[x],low[v]);
                if(low[v] >= dfn[x])
                {
                    flag ++;
                    sum[x] += (ll)Size[v] * (n - Size[v]);
                    s += Size[v];
                    //这里是判断割点的
                    if(x != 1 || flag > 1)
                        {
                           // printf("x = %d\n",x);
                            id[x] = 1;
                        }
                }
            }
            else
                low[x] = min(low[x],dfn[v]);
        }
        if(id[x])
            sum[x] += (ll)(n - s - 1) * (s + 1) + (n - 1);
        else
            sum[x] = 2 * (n - 1);
    }
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i = 1; i <= m; i ++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            Q[a].push_back(b);
            Q[b].push_back(a);
        }
        Tarjan(1);
       // printf("low = %d dfn = %d\n",low[4],dfn[4]);
        for(int i = 1; i <= n; i ++)
            printf("%lld\n",sum[i]);
    }

[https_mp.csdn.net_mdeditor]: https://mp.csdn.net/mdeditor#