bzoj1123/同洛谷P3469 BLO（无向图的割点）

今天药忘吃喽~ 2021-11-17 14:10 250阅读 0赞

## 题意：给一张无向连通图，对于每个点x，输出删掉所有与他相邻的边之后，图中有多少对点不连通。 ##

## 分析：《算法竞赛进阶指南》P399。 ##

## 代码： ##

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int N = 100010, M = 500010;
    int head[N], ver[M * 2], Next[M * 2];
    int dfn[N], low[N], Size[N];
    long long ans[N];
    bool cut[N];
    int n, m, tot, num;
    
    void add(int x, int y) {
    	ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
    }
    
    void tarjan(int x) {
    	dfn[x] = low[x] = ++num;
    	Size[x] = 1;
    	int flag = 0, sum = 0;
    	for (int i = head[x]; i; i = Next[i]) {
    		int y = ver[i];
    		if (!dfn[y]) {
    			tarjan(y);
    			Size[x] += Size[y];
    			low[x] = min(low[x], low[y]);
    			if (low[y] >= dfn[x]) {
    				flag++;
    				ans[x] += (long long)Size[y] * (n - Size[y]);
    				sum += Size[y];
    				if (x != 1 || flag > 1) cut[x] = true;
    			}
    		}
    		else low[x] = min(low[x], dfn[y]);
    	}
    	if (cut[x])
    		ans[x] += (long long)(n - sum - 1)*(sum + 1) + (n - 1);
    	else
    		ans[x] = 2 * (n - 1);
    }
    
    int main() {
    	cin >> n >> m;
    	tot = 1;
    	for (int i = 1; i <= m; i++) {
    		int x, y;
    		scanf("%d%d", &x, &y);
    		if (x == y) continue;
    		add(x, y), add(y, x);
    	}
    	tarjan(1);
    	for (int i = 1; i <= n; i++)
    		printf("%lld\n", ans[i]);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，250人围观）

还没有评论，来说两句吧...

相关阅读

相关 P3469-[POI2008]BLO-Blockade

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

- 日理万妓/ 2023年06月01日 08:57/ 0 赞/ 3 阅读

相关 POJ 2117 Electricity (无向图求割点)

题目：对于给出的无向图，删除某个顶点后，会得到多个连通分量。求最多的连通分量数（删除某点后）。每组数据的第一行两个数N和M，表示顶点和边。顶点编号0到N-1。接下来M

今天药忘吃喽~/ 2022年08月10日 14:45/ 0 赞/ 150 阅读

相关无向图的割顶（poj1523，1144）

割顶：表示无向图中的点，这个点删除之后，原图不在联通，这样的点就是割顶。怎么求一个图中的割顶呢？把无向图变成一颗树，dfs时候搜索到在dfs树上的称为树边，搜索是出

偏执的太偏执、/ 2022年08月08日 11:55/ 0 赞/ 114 阅读

相关洛谷——P1123 取数游戏

P1123 取数游戏题目描述一个N×M的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻8个格子

╰半夏微凉°/ 2021年12月24日 15:43/ 0 赞/ 268 阅读

相关洛谷P3388 模板割点

题目链接：[https://www.luogu.org/problemnew/show/P3388][https_www.luogu.org_problemnew_show_P

妖狐艹你老母/ 2021年12月10日 23:09/ 0 赞/ 237 阅读

相关 BZOJ2330/洛谷P3275（糖果）

题意： Description 幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是

阳光穿透心脏的1/2处/ 2021年11月17日 23:58/ 0 赞/ 240 阅读

相关 bzoj1123/同洛谷P3469 BLO（无向图的割点）

题意：给一张无向连通图，对于每个点x，输出删掉所有与他相邻的边之后，图中有多少对点不连通。分析：《算法竞赛进阶指南》P399。代码： includ

今天药忘吃喽~/ 2021年11月17日 14:10/ 0 赞/ 251 阅读

相关洛谷 P1123 取数游戏

题目：洛谷 P1123 取数游戏： [https://www.luogu.org/problemnew/show/P1123][https_www.luogu.org_pro

青旅半醒/ 2021年11月05日 13:54/ 1 赞/ 418 阅读

相关【洛谷 3388】割点

题目背景割点题目描述给出一个nnn个点，mmm条边的无向图，求图的割点。输入输出格式输入格式：第一行输入n,mn,mn,m 下面mm

水深无声/ 2021年10月26日 21:46/ 0 赞/ 304 阅读

相关【洛谷P3388】【模板】割点

都快忘了割点怎么搞了对所有点分两类 1.根节点 2.非根节点显然根节点是很好做的只需要数一下有没有两个子树以上对于非根节点利用tarjan算法回忆到dfn

Dear 丶/ 2021年09月29日 23:10/ 0 赞/ 363 阅读