POJ3694NetworkTarjan求边双连通+LCS+并查集

作者：古韵卡次 | 来源：互联网 | 2023-09-23 23:53

POJ3694NetworkTarjan求边双连通+LCS+并查集题目链接：POJ3694Network题意：给定N个顶点M条边的无向图。N(1≤N≤100,0

POJ 3694 Network Tarjan求边双连通+LCS+并查集

题目链接： POJ 3694 Network

题意：给定 N个顶点M条边的无向图。N(1 ≤ N ≤ 100,000) and M(N - 1 ≤ M ≤ 200,000). 数据保证 图是连通的。然后Q个操作(Q <1000)，每次往图中添加一条边，每次操作之后给出图中还有多少个桥(割边)。

思路：这是一道很有意思的题目！首先对原图进行边双连通缩点，求出DAG，因为初始的无向图是连通的，那么求出来的DAG是一棵树（PS：为了以后求LCA，我需要保存每个节点的父节点和深度），树上的边全是桥，这是无向连通图的性质嘛。

求出DAG树之后，我们理解为我们新构建了一个 有向图。

然后每次添加一条边(u, v)，如果两个顶点在原图中的同一个边双连通，毫无疑问，不需要处理。反之，就向上找最近公共祖先节点设为x，并把沿途的节点加入并查集中，因为添加一条边，相当于在树上增加一条边，即形成了 u → x → v 的一个环，那么 环上所有的边都不是桥了，这是显而易见的。

求公共祖先节点的时候利用了 并查集压缩路径 的一个思想，DAG图中，同一个强连通分量中，深度高的节点直接跳转到他的祖先的位置（我让祖先一定是同一个强连通分量中深度最低的节点，并查集中合并的时候可以保证到这点），这样就不必要一个个向上走了，这个在代码中有所体现。

这样就是344MS水过了。

测试数据可以参考 Discuss 提供的测试数据。注意， 无向图边数要开双倍，时刻记住，谨记谨记~

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define fst             first
#define snd             second
typedef __int64			LL;
typedef pair	PII;

const int MAXN = 100000 + 5;
const int MAXM = 200000 + 5;

struct Edge {
	int v, next;
	Edge() {}
	Edge(int v, int next) : v(v), next(next) {}
} edge[MAXM <<1];
struct TNode {
	int fa, depth;
	TNode() {}
	TNode(int fa, int depth) : fa(fa), depth(depth) {}
} tree[MAXN];
int head[MAXN], tot;
int low[MAXN], dfn[MAXN], belong[MAXN], stack[MAXN], top, Index, bridge, block;
bool inStack[MAXN];
bool vis[MAXN];
int par[MAXN];
int N, M, Q;

void init() {
	block = bridge = tot = Index = top = 0;
	memset(head, -1, sizeof(head));
	memset(dfn, 0, sizeof(dfn));
	memset(inStack, false, sizeof(inStack));
	memset(vis, false, sizeof(vis));
}
void add_edge(int& u, int& v) {
	edge[tot] = Edge(v, head[u]);
	head[u] = tot++;
}
void Tarjan(int u, int pre) {
	int v;
	low[u] = dfn[u] = ++Index;
	stack[top++] = u;
	inStack[u] = true;
	bool flag = false; // 跳过反向边
	for (int i = head[u]; ~i; i = edge[i].next) {
		v = edge[i].v;
		if (v == pre && !flag) {
			flag = true;
			continue;
		}
		if (!dfn[v]) {
			Tarjan(v, u);
			if (low[u] > low[v]) low[u] = low[v];
			if (low[v] > dfn[u]) {
				bridge ++;
			}
		} else if (inStack[v] && low[u] > dfn[v]) low[u] = dfn[v];
	}
	if (low[u] == dfn[u]) {
		block++;
		do {
			v = stack[--top];
			inStack[v] = false;
			belong[v] = block;
		} while (u != v);
	}
}
void build_tree(const int u, const int pre, const int depth) {
	int v;
	vis[u] = true;
	tree[belong[u]] = TNode(belong[pre], depth);
	for (int i = head[u]; ~i; i = edge[i].next) {
		v = edge[i].v;
		if (vis[v]) continue;
		if (v == pre) continue;
		build_tree(v, u, belong[u] == belong[v] ? depth : depth + 1);
	}
}
int Find(const int x) {
	return x == par[x] ? x : (par[x] = Find(par[x]));
}
void Union(const int& a, const int& b) {
	int pa = Find(a), pb = Find(b);
	if (pa == pb) return;
	par[pa] = pb;
	Find(a), Find(b);
}
void lca(int a, int b) {
	if (Find(a) == Find(b)) return;
	while (tree[a].depth 		if (Find(tree[b].fa) != Find(b)) bridge --;
		Union(b, tree[b].fa);
		b = Find(b);
	}
	while (tree[a].depth > tree[b].depth) {
		if (Find(tree[a].fa) != Find(a)) bridge --;
		Union(a, tree[a].fa);
		a = Find(a);
	}
	while (a != b) {
		if (Find(tree[a].fa) != Find(a)) bridge --;
		if (Find(tree[b].fa) != Find(b)) bridge --;
		Union(a, tree[a].fa);
		Union(b, tree[b].fa);
		a = Find(a);
		b = Find(b);
	}
}

int main() {
#ifndef ONLINE_JUDGE
	FIN;
#endif // ONLINE_JUDGE
	int u, v, cas = 0;
	while (~scanf("%d %d", &N, &M) && N) {
		init();
		for (int i = 0; i 			scanf("%d %d", &u, &v);
			add_edge(u, v);
			add_edge(v, u);
		}
		Tarjan(1, 0);
		build_tree(1, 1, 1);
		for (int i = 1; i <= block; i++) par[i] = i;
		scanf("%d", &Q);
		printf("Case %d:\n", ++cas);
		while (Q--) {
			scanf("%d %d", &u, &v);
			lca(belong[u], belong[v]);
			printf("%d\n", bridge);
		}
		puts("");
	}
	return 0;
}

推荐阅读

io
视觉Transformer综述

本文综述了视觉Transformer在计算机视觉领域的应用，从原始Transformer出发，详细介绍了其在图像分类、目标检测和图像分割等任务中的最新进展。文章不仅涵盖了基础的Transformer架构，还深入探讨了各类增强版Transformer模型的设计思路和技术细节。 ... [详细]

蜡笔小新 2024-11-22 19:53:16
io
如何在没有提交按钮的情况下提交HTML表单？

探讨了在HTML表单中使用元素代替进行表单提交的方法。 ... [详细]

蜡笔小新 2024-11-22 17:48:42
io
WPF菜单控件前景与背景颜色设置指南

尽管在WPF中工作了一段时间，但在菜单控件的样式设置上遇到了一些基础问题，特别是关于如何正确配置前景色和背景色。 ... [详细]

蜡笔小新 2024-11-22 15:30:54
settings
解决iOS应用推送通知错误：未找到有效aps-environment权限

在尝试加载支持推送通知的iOS应用程序的Ad Hoc构建时，遇到了‘no valid aps-environment entitlement found for application’的错误提示。本文将探讨此错误的原因及多种可能的解决方案。 ... [详细]

蜡笔小新 2024-11-21 19:26:31
io
UVALive 8201 - BBP 公式计算圆周率

在1995年，Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后，Bailey 和 Borwein 在他们的论文中发表了这一发现，这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]

蜡笔小新 2024-11-21 18:32:57
io
阶段一：Hankson的趣味数学挑战——不使用辗转相除法求解特定条件下的正整数

Hanks博士是一位著名的生物技术专家，他的儿子Hankson对数学有着浓厚的兴趣。最近，Hankson遇到了一个有趣的数学问题，涉及求解特定条件下的正整数x，而不使用传统的辗转相除法。 ... [详细]

蜡笔小新 2024-11-22 14:26:49
io
深入解析C语言中的关键字及其分类

本文将全面介绍C语言中的关键字，并按照功能将其分为数据类型关键字、控制结构关键字、存储类别关键字和其他关键字四大类，旨在帮助读者更好地理解和运用这些基本元素。C语言中共有32个关键字。 ... [详细]

蜡笔小新 2024-11-22 09:55:47
数组
H5技术实现经典游戏《贪吃蛇》

本文将分享一个使用HTML5技术实现的经典小游戏——《贪吃蛇》。通过H5技术，我们将探讨如何构建这款游戏的两种主要玩法：积分闯关和无尽模式。 ... [详细]

蜡笔小新 2024-11-21 20:16:59
io
D17：C#设计模式之十六观察者模式（Observer Pattern）【行为型】

一、引言今天是2017年11月份的最后一天，也就是2017年11月30日，利用今天再写一个模式，争取下个月（也就是12月份& ... [详细]

蜡笔小新 2024-11-22 19:45:55
io
服务器虚拟化存储设计,完美规划储存与资源，部署高性能虚拟化桌面

规划部署虚拟桌面环境前，必须先估算目前所使用实体桌面环境的工作负载与IOPS性能，并慎选储存设备。唯有谨慎估算贴近实际的IOPS性能，才能 ... [详细]

蜡笔小新 2024-11-22 19:12:09
io
DedeCMS 手机端站点配置与优化指南

本文详细介绍如何安装和配置DedeCMS的移动端站点，包括新版本安装、老版本升级、模板适配以及必要的代码修改，以确保移动站点的正常运行。 ... [详细]

蜡笔小新 2024-11-22 18:44:25
io
黑客松获奖名单出炉、NFT艺术周圆满落幕 |Oasis周报

黑客松获奖名单出炉、NFT艺术周圆满落幕 |Oasis周报 ... [详细]

蜡笔小新 2024-11-22 18:23:40
io
解析 .NET 中的 AJAX 技术

Asynchronous JavaScript and XML (AJAX) 的流行很大程度上得益于 Google 在其产品如 Google Suggest 和 Google Maps 中的应用。本文将深入探讨 AJAX 在 .NET 环境下的工作原理及其实现方法。 ... [详细]

蜡笔小新 2024-11-22 18:18:57
io
吴石访谈：腾讯安全科恩实验室如何引领物联网安全研究

腾讯安全科恩实验室曾两次成功破解特斯拉自动驾驶系统，并远程控制汽车，展示了其在汽车安全领域的强大实力。近日，该实验室负责人吴石接受了InfoQ的专访，详细介绍了团队未来的重点方向——物联网安全。 ... [详细]

蜡笔小新 2024-11-22 13:27:32
io
Fiddler 安装与配置指南

本文详细介绍了Fiddler的安装步骤及配置方法，旨在帮助用户顺利抓取用户Token。文章还涵盖了一些常见问题的解决方案，以确保安装过程顺利。 ... [详细]

蜡笔小新 2024-11-22 11:36:57

古韵卡次

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章