2020ICPC·小米 网络选拔赛第一场 D - Router Mesh（求删掉割点后的连通块数）

链接：https://ac.nowcoder.com/acm/contest/7501/D
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

In a Mesh networking system, there are nn_{}n​ MI Routers, where mm_{}m​ pairs of MI Routers are bidirectionally connected. In order to check the stability of the system, for each MI Router, we should determine the number of connected components after removing it and relative connections from the system. And then assess that if we should add more MI Routers into the system. Print the numbers of connected components in residual system after removing each MI Router.

输入描述:

The first line contains two integers n,m (1≤n,m≤3×105)n,m~(1\le n,m\le 3\times 10^5)n,m (1≤n,m≤3×105), denoting the number of MI Routers and bidirectional connections in the Mesh networking system.

Following mm_{}m​ lines each contains two integers u,v (1≤u<v≤n)u,v~(1 \le u < v \le n)u,v (1≤u<v≤n), denoting the uu_{}u​-th MI Router has a bidirectional connection with the vv_{}v​-th MI Router.

It's guaranteed that there are no duplicated connections in input.

输出描述:

Print one line containing nn_{}n​ integers, where ii_{}i​-th integer denotes the number of connected components after removing ii_{}i​-th MI Router and relative connections.

示例1

输入

4 2
1 2
1 3

输出

3 2 2 1

说明

After removing the 1st MI Router and relative connections, there are 33_{}3​ connected components: {2},{3},{4}\{2\}, \{3\}, \{4\}_{}{2},{3},{4}​.
After removing the 2nd MI Router and relative connections, there are 22_{}2​ connected components: {1,3},{4}\{1, 3\}, \{4\}_{}{1,3},{4}​.
After removing the 3rd MI Router and relative connections, there are 22_{}2​ connected components: {1,2},{4}\{1, 2\}, \{4\}_{}{1,2},{4}​.
After removing the 4th MI Router and relative connections, there is only 11_{}1​ connected component: {1,2,3}\{1, 2, 3\}_{}{1,2,3}​.

题意：

给一个不一定连通的无向图，问删掉每个点后剩余的连通块数

tarjan求割点和删掉后剩余的连通块数。存个板子

https://blog.csdn.net/qq547276542/article/details/47782369

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
const int MAXN=300010,MAXM=600010;
//点的下标切记转换成由1~n
struct Edge{
   int to,next;
   bool cut;  //是否为桥的标记*******
}edge[MAXM];  //边数组
/*    遍历点u的临接边
    for(int i=head[u];i!=-1;i=edge[i].next)
    {   edge[i]      } //edge[i]即为边
*/
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN];
int Index,top;
bool Instack[MAXN];
bool cut[MAXN];    //是否为割点的标记*********
int add_block[MAXN];   //删除一个点后增加的连通块
int bridge;     //记录桥的个数*******
int n, m;

void init(){  //加边前先初始化
   memset(DFN,0,sizeof(DFN));
   memset(Instack,false,sizeof(Instack));
   memset(add_block,0,sizeof(add_block));
   memset(cut,false,sizeof(cut));
   memset(head,-1,sizeof(head));
   tot=Index=top=bridge=0;
}

void add_edge(int u,int v){  ///添加无向边，只需调用一次！！！！
    edge[tot].to=v;  edge[tot].next=head[u] ; edge[tot].cut=false;
    head[u]=tot++;
    edge[tot].to=u;  edge[tot].next=head[v] ; edge[tot].cut=false;
    head[v]=tot++;
}

void Tarjan(int u,int pre){
    int v;
    Low[u]=DFN[u]=++Index;
    Stack[top++]=u;
    Instack[u]=true;
    int son=0;
    for(int i=head[u];i!=-1;i=edge[i].next){
         v=edge[i].to;
         if(v==pre)continue;
         if(!DFN[v]){     //如果没有访问过v
            son++;
            Tarjan(v,u);
            if(Low[u]>Low[v])Low[u]=Low[v];
            //判断无向边（u,v）是否是桥
            if(Low[v]>DFN[u]){
                bridge++;
                edge[i].cut=true;
                edge[i^1].cut=true;
            }
            //判断u是否为割点
            if(u!=pre&&Low[v]>=DFN[u]){
                cut[u]=true;
                add_block[u]++;
            }
         }
         else if(Low[u]>DFN[v])
            Low[u]=DFN[v];
    }
    if(u==pre&&son>1)cut[u]=true;
    if(u==pre)add_block[u]=son-1;
    Instack[u]=false;
    top--;
}

void solve(int N){  //  寻找割顶和桥,N为题目中结点数
     for(int i=1;i<=N;i++)    //防止图不连通
     if(!DFN[i])Tarjan(i,i);     //对于每一个连通分量都调用一次
}

bool vis[MAXN];
void dfs(int u) {
    vis[u] = 1;
    for(int i = head[u]; ~i; i = edge[i].next)
        if(!vis[edge[i].to])
            dfs(edge[i].to);
}

int main() {
    scanf("%d%d", &n, &m);
    int u, v;
    init();
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        add_edge(u, v);
    }
    solve(n);
    memset(vis, 0, sizeof(vis));
    int all = 0;
    for(int i = 1; i <= n; ++i) {
        if(!vis[i]) {
            dfs(i);
            all++;
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(i > 1) printf(" ");
        printf("%d", all + add_block[i]);
    }
    printf("\n");
    return 0;
}

 

本文地址：https://blog.csdn.net/weixin_43871207/article/details/109278199