2020ICPC·小米网络选拔赛第一场 Router Mesh

本文主要是介绍2020ICPC·小米网络选拔赛第一场 Router Mesh，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

https://ac.nowcoder.com/acm/contest/7501

题意

求出图中删去每个点后联通块数目

思路

tarjan算法求割点修改

维护dfn和low数组，对于边u-v，如果low[v]>=dfn[u]，说明只可以通过u到达v，u是割点，删除u会增加一个连通数，那我们记录增加的连通数个数，记为tmp。当u不是树根时，删点后父亲也是一个分量，那么删去后联通块数目从1变到了tmp+1，如果是树根，则是从1变到了tmp。我们记变成的联通块个数为ans。那么对于删去的每个点，联通块个数是从初始C变为了C-1+ans。C可以通过main函数调用tarjan个数求得。

代码

//处理无向图，
//low代表不经过父亲可达最小时间戳
//dfs遍历，回溯更新low，如果u-v且v的low比u的时间戳大于等于，说明必须经过父亲才能回根
//则一定为割点。
//关于u==father的问题，这种情况只会在dfs树根出现，如果根连着两个以上是需要记录的，
//如果不加条件dfs树根比被判定为割点，这种情况是荒谬的
//而对于子树树根，它如果是割点是会被记录的//割边时不用考虑low[v]=dfn[u]时情况，并且也不用考虑son数量的问题
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
//#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=1e6+5;const int maxe=1e6+5;const int inf=0x3f3f3f3f;int dfn[maxn],low[maxn],dfncnt;//low数组为某点不经其父亲到达的最小dfnint ans[maxn];int cnt;int head[maxe];struct Edge{int next;int to;int dis; } edge[maxe]; void init(){memset(head,-1,sizeof(head));cnt=0;}void add(int u,int v,int w){edge[cnt].dis=w;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}void tarjan(int u,int father) {low[u] = dfn[u] = ++dfncnt;if(u==father)   ans[u]=0;else            ans[u]=1;for (int i = head[u]; ~i ; i=edge[i].next) {int v = edge[i].to;if (!dfn[v]) {tarjan(v,u);low[u] = min(low[u], low[v]);if(low[v]>=dfn[u])ans[u]++;}else if (v!=father) {low[u] = min(low[u], dfn[v]);}}} int main(){IOS#ifndef ONLINE_JUDGEfreopen("D:\\code\\IO\\in.txt","r",stdin);freopen("D:\\code\\IO\\out.txt","w",stdout);#endifint n,m;cin>>n>>m;init();while(m--){int u,v;cin>>u>>v;add(u,v,0);add(v,u,0);}int total=0;for(int i=1;i<=n;i++)if(!dfn[i]){total++;tarjan(i,i);}for(int i=1;i<=n;i++){cout<<total+ans[i]-1;if(i!=n)    cout<<" ";else        cout<<endl;}}