2020小米网络赛第一场 D Router Mesh（点双连通分量）

本文主要是介绍2020小米网络赛第一场 D Router Mesh（点双连通分量），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
一个图，求出删掉每个点后得到的连通块数量。

思路：
算出每个点所在的点双连通分量数目$vis[i]$，就可以得出这个点删掉后增加的连通块数目了。同时算出初始的连通块数目$all$，则删掉点$i$的连通块数目为$vis[i]+all-1$。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>using namespace std;typedef long long ll;const int mod = 1e9 + 7;
const int maxn = 3e5 + 7;
int head[maxn], to[maxn * 2], nex[maxn * 2],tot;
int dfn[maxn], low[maxn], stack[maxn];
int cut[maxn],vis[maxn];
vector<int>dcc[maxn];
int num,top,cnt;
int root;void add(int x,int y) {to[++tot] = y;nex[tot] = head[x];head[x] = tot;
}void tarjan(int x) {dfn[x] = low[x] = ++num;stack[++top] = x;int flag = 0;if (x == root && head[x] == 0) { // 孤立点dcc[++cnt].push_back(x);return;}for (int i = head[x]; i; i = nex[i]) {int y = to[i];if (!dfn[y]) {tarjan(y);low[x] = min(low[x], low[y]);if (low[y] >= dfn[x]) {flag++;if (x != root || flag > 1) cut[x] = true;cnt++;int z;do {z = stack[top--];dcc[cnt].push_back(z);vis[z]++;} while (z != y);dcc[cnt].push_back(x);vis[x]++;}}else low[x] = min(low[x], dfn[y]);}
}int fa[maxn];
int findset(int x) {if(fa[x] == x) return x;return fa[x] = findset(fa[x]);
}
void Union(int x,int y) {int rx = findset(x),ry = findset(y);if(rx != ry) {fa[rx] = ry;}
}int main() {int n,m;scanf("%d%d",&n,&m);for(int i = 1;i <= n;i++) fa[i] = i;for(int i = 1;i <= m;i++) {int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);Union(x,y);}int all = 0;for(int i = 1;i <= n;i++) {if(!dfn[i]) {tarjan(i);}if(fa[i] == i) all++;}for(int i = 1;i <= n;i++) {printf("%d ",all + vis[i] - 1);}return 0;
}

这篇关于2020小米网络赛第一场 D Router Mesh（点双连通分量）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---