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;
}

推荐阅读

ip
Comet OJ - Contest #2 B　她的想法、他的战斗（概率　＋　数学）

题目描述Takuru是一名情报强者，所以他想利用他强大的情报搜集能力来当中间商赚差价。Takuru的计划是让Hinae帮他去市场上买一个商品，然后再以另一个价格卖掉它。Takur ... [详细]

蜡笔小新 2023-10-15 11:48:13
int
差分约束系统求解House Man跳跃问题的思路与方法

本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度，要求从最低点跳跃到最高点，每次跳跃的距离不超过D，并且不能改变给定的顺序。通过建立差分约束系统，将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法，并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]

蜡笔小新 2023-12-14 11:49:51
ip
CF：3D City Model（小思维）问题解析和代码实现

本文通过解析CF：3D City Model问题，介绍了问题的背景和要求，并给出了相应的代码实现。该问题涉及到在一个矩形的网格上建造城市的情景，每个网格单元可以作为建筑的基础，建筑由多个立方体叠加而成。文章详细讲解了问题的解决思路，并给出了相应的代码实现供读者参考。 ... [详细]

蜡笔小新 2023-12-13 14:17:11
ip
树莓派语音控制的配置方法和步骤

本文介绍了在树莓派上实现语音控制的配置方法和步骤。首先感谢博主Eoman的帮助，文章参考了他的内容。树莓派的配置需要通过sudo raspi-config进行，然后使用Eoman的控制方法，即安装wiringPi库并编写控制引脚的脚本。具体的安装步骤和脚本编写方法在文章中详细介绍。 ... [详细]

蜡笔小新 2023-12-12 03:02:49
main
开发笔记：使用Junit和黄瓜进行自动化测试步骤缺失

本文由编程笔记小编整理，主要介绍了使用Junit和黄瓜进行自动化测试中步骤缺失的问题。文章首先介绍了使用cucumber和Junit创建Runner类的代码，然后详细说明了黄瓜功能中的步骤和Steps类的实现。本文对于需要使用Junit和黄瓜进行自动化测试的开发者具有一定的参考价值。摘要长度：187字。 ... [详细]

蜡笔小新 2023-12-11 20:20:32
int
Codeforces Round #321 (Div. 2) Kefa and Dishes 状压+spfa

本文介绍了Codeforces Round #321 (Div. 2)比赛中的问题Kefa and Dishes，通过状压和spfa算法解决了这个问题。给定一个有向图，求在不超过m步的情况下，能获得的最大权值和。点不能重复走。文章详细介绍了问题的题意、解题思路和代码实现。 ... [详细]

蜡笔小新 2023-12-11 10:37:34
int
linux进阶50——无锁CAS

1.概念比较并交换(compareandswap，CAS)，是原⼦操作的⼀种，可⽤于在多线程编程中实现不被打断的数据交换操作࿰ ... [详细]

蜡笔小新 2023-12-09 10:10:40
int
拆点+KM，建图思路看的题解，求解最小权匹配问题

本文介绍了一种求解最小权匹配问题的方法，使用了拆点和KM算法。通过将机器拆成多个点，表示加工的顺序，然后使用KM算法求解最小权匹配，得到最优解。文章给出了具体的代码实现，并提供了一篇题解作为参考。 ... [详细]

蜡笔小新 2023-12-09 09:24:15
ip
七月在线爬虫班学习笔记（七）——高级内容-并发编程

第七课主要内容：多进程多线程FIFO,LIFO,优先队列线程局部变量进程与线程的选择线程池异步IO概念及twisted案例股票数据抓取 ... [详细]

蜡笔小新 2023-10-17 20:16:36
int
Codeforces Round #383 (Div. 2) D 分组背包

给出一群女孩的重量和颜值和她们的朋友关系现在有一个舞台ab是朋友bc是朋友ac就是朋友给出最大承重可以邀请这些女孩来玩对于每一个朋友团体全邀请or邀请一个or不邀请问能邀请的女孩的 ... [详细]

蜡笔小新 2023-10-17 17:22:42
ip
[翻译]PyCairo指南裁剪和masking

裁剪和masking在PyCairo指南的这个部分，我么将讨论裁剪和masking操作。裁剪裁剪就是将图形的绘制限定在一定的区域内。这样做有一些效率的因素࿰ ... [详细]

蜡笔小新 2023-10-17 17:18:21
int
51nod3221祝寿(反向建图优化)

题目链接感觉忘记了好多东西。求有向图中其余点到一个点的最短距离可以将该图翻转后rundijkstra#include#include ... [详细]

蜡笔小新 2023-10-17 14:12:39
ip
rabbitmq杂谈

rabbitmq中的consumerTag和deliveryTag分别是干啥的，有什么用？同一个会话，consumerTag是固定的可以做此会话的名字，deliveryTag每次接 ... [详细]

蜡笔小新 2023-10-17 12:46:24
int
一文了解Python collections模块中的deque用法[python头条资讯]

Python中文网有大量免费的Python入门教程，欢迎大家来学习。collections是Python内建的一个集合模块，deque是双边队列，具有队列和栈的性质，在list的基 ... [详细]

蜡笔小新 2023-10-16 14:22:02
int
[APIO2012]派遣解题报告

796.[APIO2012]派遣在一个忍者的帮派里，一些忍者们被选中派遣给顾客，然后依据自己的工作获取报偿。在这个帮派里，有一名忍者被称之为Master。 ... [详细]

蜡笔小新 2023-10-15 20:32:49

古韵卡次

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

Tags | 热门标签

RankList | 热门文章