首页 > 其他分享 >230623 做题记录 // 强连通分量

230623 做题记录 // 强连通分量

时间：2023-06-23 11:11:05浏览次数：38  
标签：连通 return int 230623 read dfn maxn low 分量

哈→啊↗ / 哈→啊↗啊↘ / 哈↘ / 哈→啊↗啊↘啊→ / 啊→啊↘啊↘啊→ / 哈↗啊→啊↘啊→ / 哈↗啊→啊↘啊↘ / 哈→啊↘啊↗啊↘

原曲：花与树的女儿们

A. 时间戳

http://222.180.160.110:1024/contest/3698/problem/1

？合着强制链式前向星？邻接表党震怒！

所以决定 reverse……

namespace XSC062 {
using namespace fastIO;
const int maxn = 15;
int dfn[maxn];
int n, m, x, y, now;
std::vector<int> g[maxn];
void DFS(int x) {
	dfn[x] = ++now;
	for (auto i : g[x]) {
		if (dfn[i] == 0)
			DFS(i);
	}
	return;
}
inline void add(int x, int y) {
	g[x].push_back(y);
	return;
}
int main() {
	read(n), read(m);
	while (m--) {
		read(x), read(y);
		add(x, y), add(y, x);
	}
	for (int i = 1; i <= n; ++i)
		std::reverse(g[i].begin(), g[i].end());
	DFS(1);
	for (int i = 1; i <= n; ++i)
		print(dfn[i], '\n');
	return 0;
}
} // namespace XSC062

B. 割点和割边

http://222.180.160.110:1024/contest/3698/problem/2

说好的今天全是强连通分量呢，，，

namespace XSC062 {
using namespace fastIO;
const int maxn = 5e3 + 5;
int dfn[maxn], low[maxn];
std::vector<int> g[maxn];
int n, m, x, y, now, rt, cntv, cntw;
inline int min(int x, int y) {
	return x < y ? x : y;
}
void DFS(int x, int fa) {
	bool cut = 0;
	dfn[x] = low[x] = ++now;
	for (auto i : g[x]) {
		if (!dfn[i]) {
			DFS(i, x);
			low[x] = min(low[x], low[i]);
			if (low[i] >= dfn[x]) {
				if (fa != -1 || ++rt >= 2)
					cut = 1;
			}
			if (low[i] > dfn[x])
				++cntw;
		}
		else if (i != fa)
			low[x] = min(low[x], dfn[i]);
	}
	cntv += cut;
	return;
}
inline void add(int x, int y) {
	g[x].push_back(y);
	return;
}
int main() {
	read(n), read(m);
	while (m--) {
		read(x), read(y);
		add(x, y), add(y, x);
	}
	DFS(1, -1);
	print(cntv, '\n');
	print(cntw, '\n');
	return 0;
}
} // namespace XSC062

C. 点双连通分量

http://222.180.160.110:1024/contest/3698/problem/3

题目背景

注：本题需要链式前向星建图

好的，我用邻接表。

namespace XSC062 {
using namespace fastIO;
const int maxn = 5e4 + 5;
std::stack<int> t;
int dfn[maxn], low[maxn];
int n, m, x, y, now, rt, cntv;
std::vector<int> g[maxn], scc[maxn];
inline int min(int x, int y) {
	return x < y ? x : y;
}
void DFS(int x, int fa) {
	t.push(x);
	dfn[x] = low[x] = ++now;
	for (auto i : g[x]) {
		if (!dfn[i]) {
			DFS(i, x);
			low[x] = min(low[x], low[i]);
			if (low[i] >= dfn[x]) {
				++cntv;
				int p;
				do {
					p = t.top();
					t.pop();
					scc[cntv].push_back(p);
				} while (p != i);
				scc[cntv].push_back(x);
			}
		}
		else if (i != fa)
			low[x] = min(low[x], dfn[i]);
	}
	return;
}
inline void add(int x, int y) {
	g[x].push_back(y);
	return;
}
int main() {
	read(n), read(m);
	while (m--) {
		read(x), read(y);
		add(x, y), add(y, x);
	}
	DFS(1, -1);
	print(cntv, '\n');
	for (int i = 1; i <= cntv; ++i) {
		print(scc[i].size(), ' ');
		for (auto j : scc[i])
			print(j, ' ');
		putchar('\n');
	}
	return 0;
}
} // namespace XSC062

D. 边双连通分量

http://222.180.160.110:1024/contest/3698/problem/4

为什么全是板子？？？

woc，WA 了。

我你妈，图不连通。

namespace XSC062 {
using namespace fastIO;
const int maxn = 5e4 + 5;
int dfn[maxn], low[maxn];
std::vector<int> g[maxn];
int n, m, x, y, now, cntw;
inline int min(int x, int y) {
	return x < y ? x : y;
}
void DFS(int x, int fa) {
	dfn[x] = low[x] = ++now;
	for (auto i : g[x]) {
		if (!dfn[i]) {
			DFS(i, x);
			low[x] = min(low[x], low[i]);
		}
		else if (i != fa)
			low[x] = min(low[x], dfn[i]);
	}
	if (low[x] == dfn[x])
		++cntw;
	return;
}
inline void add(int x, int y) {
	g[x].push_back(y);
	return;
}
int main() {
	read(n), read(m);
	while (m--) {
		read(x), read(y);
		add(x, y), add(y, x);
	}
	for (int i = 1; i <= n; ++i) {
		if (dfn[i] == 0)
			DFS(i, -1);
	}
	print(cntw, '\n');
	return 0;
}
} // namespace XSC062

E. 绮丽的天空

http://222.180.160.110:1024/contest/3698/problem/5

强连通分量缩点然后 SPFA 或者 Topo 吧。

感觉 Topo 搭坡会好写一点。

namespace XSC062 {
using namespace fastIO;
const int maxn = 5e5 + 5;
#define mkp std::make_pair
using pii = std::pair<int, int>;
std::set<pii> u;
std::stack<int> t;
std::queue<int> q;
int a[maxn], col[maxn];
int n, m, x, y, now, cntw;
std::vector<int> g[maxn], g1[maxn];
int dfn[maxn], low[maxn], deg[maxn];
int mx[maxn], su[maxn], fm[maxn], fs[maxn];
inline int min(int x, int y) {
	return x < y ? x : y;
}
inline int max(int x, int y) {
	return x > y ? x : y;
}
void DFS(int x) {
	t.push(x);
	dfn[x] = low[x] = ++now;
	for (auto i : g[x]) {
		if (!dfn[i]) {
			DFS(i);
			low[x] = min(low[x], low[i]);
		}
		else if (!col[i])
			low[x] = min(low[x], dfn[i]);
	}
	if (low[x] == dfn[x]) {
		int p;
		++cntw;
		do {
			p = t.top();
			t.pop();
			mx[cntw] = max(mx[cntw], a[p]);
			su[cntw] += a[p];
			col[p] = cntw;
		} while (p != x);
	}
	return;
}
inline void add(int x, int y) {
	g[x].push_back(y);
	return;
}
inline void _add(int x, int y) {
	g1[x].push_back(y);
	return;
}
inline void Topo(void) {
	for (int i = 1; i <= cntw; ++i) {
		fm[i] = mx[i];
		fs[i] = su[i];
		if (deg[i] == 0)
			q.push(i);
	}
	while (!q.empty()) {
		int f = q.front();
		q.pop();
		for (auto i : g1[f]) {
			if (fs[f] + su[i] > fs[i]) {
				fs[i] = fs[f] + su[i];
				fm[i] = max(fm[f], mx[i]);
			}
			else if (fs[f] + su[i] == fs[i])
				fm[i] = max(fm[f], fm[i]);
			if (--deg[i] == 0)
				q.push(i);
		}
	}
	return;
}
int main() {
	read(n), read(m);
	for (int i = 1; i <= n; ++i)
		read(a[i]);
	while (m--) {
		read(x), read(y);
		add(x, y);
	}
	for (int i = 1; i <= n; ++i) {
		if (dfn[i] == 0)
			DFS(i);
	}
	for (int i = 1; i <= n; ++i) {
		for (auto j : g[i]) {
			if (col[i] == col[j])
				continue;
			if (u.find(mkp(col[i], col[j]))
								!= u.end())
				continue;
			u.insert(mkp(col[i], col[j]));
			_add(col[i], col[j]);
			++deg[col[j]];
		}
	}
	Topo();
	int su = 0, mx = 0;
	for (int i = 1; i <= n; ++i) {
		if (fs[i] > su)
			su = fs[i], mx = fm[i];
		else if (fs[i] == su)
			mx = max(mx, fm[i]);
	}
	print(su, ' '), print(mx, '\n');
	return 0;
}
} // namespace XSC062

F. Grass Cownoisseur

http://222.180.160.110:1024/contest/3698/problem/6

woc，一大堆英语吓死我，往下划了半天居然有翻译。

其实应该挺简单的，还是 SPFA 一下（注意因为规定了起点所以不能用拓扑）就好了。

因为强连通分量缩完点之后是一个 DAG，当我们反向一条边后可能会出现至多一个环，而我们需要的路径就是这个环。

接下来就要寻找反向边出现的位置。以 1 为起点跑一个 SPFA，再建个反图以 1 为起点跑一个 SPFA，这样我们就得到了 1 到达每个点和每个点回到 1 的最长路。

枚举每一条边 \((u, v)\) 作为反向边的情况，该情况下的答案就是 \(1\to v\) 和 \(u \to 1\) 的最长路之和（前提是两端点均可达 1 号点），在所有边中找到最大值即可。

namespace XSC062 {
using namespace fastIO;
const int maxn = 1e5 + 5;
#define mkp std::make_pair
using pii = std::pair<int, int>;
bool in[maxn];
std::set<pii> u;
std::stack<int> t;
std::queue<int> q;
std::vector<int> g[maxn];
int n, m, x, y, now, cntw, res;
int siz[maxn], d1[maxn], d2[maxn];
int col[maxn], dfn[maxn], low[maxn];
std::vector<int> g1[maxn], g2[maxn];
inline int min(int x, int y) {
	return x < y ? x : y;
}
inline int max(int x, int y) {
	return x > y ? x : y;
}
void DFS(int x) {
	t.push(x);
	dfn[x] = low[x] = ++now;
	for (auto i : g[x]) {
		if (!dfn[i]) {
			DFS(i);
			low[x] = min(low[x], low[i]);
		}
		else if (!col[i])
			low[x] = min(low[x], dfn[i]);
	}
	if (low[x] == dfn[x]) {
		int p;
		++cntw;
		do {
			p = t.top();
			t.pop();
			++siz[cntw];
			col[p] = cntw;
		} while (p != x);
	}
	return;
}
inline void SPFA1(int s) {
	memset(d1, -0x3f, sizeof (d1));
	q.push(s);
	in[s] = 1;
	d1[s] = siz[s];
	while (!q.empty()) {
		int f = q.front();
		q.pop();
		in[f] = 0;
		for (auto i : g1[f]) {
			if (d1[i] < d1[f] + siz[i]) {
				d1[i] = d1[f] + siz[i];
				if (!in[i])
					in[i] = 1, q.push(i);
			}
		}
	}
	return;
}
inline void SPFA2(int s) {
	memset(d2, -0x3f, sizeof (d2));
	q.push(s);
	in[s] = 1;
	d2[s] = 0;
	while (!q.empty()) {
		int f = q.front();
		q.pop();
		in[f] = 0;
		for (auto i : g2[f]) {
			if (d2[i] < d2[f] + siz[i]) {
				d2[i] = d2[f] + siz[i];
				if (!in[i])
					in[i] = 1, q.push(i);
			}
		}
	}
	return;
}
inline void add(int x, int y) {
	g[x].push_back(y);
	return;
}
inline void _add(int x, int y) {
	g1[x].push_back(y);
	return;
}
inline void add_(int x, int y) {
	g2[x].push_back(y);
	return;
}
int main() {
	read(n), read(m);
	while (m--) {
		read(x), read(y);
		add(x, y);
	}
	for (int i = 1; i <= n; ++i) {
		if (dfn[i] == 0)
			DFS(i);
	}
	for (int i = 1; i <= n; ++i) {
		for (auto j : g[i]) {
			if (col[i] == col[j])
				continue;
			if (u.find(mkp(col[i], col[j]))
								!= u.end())
				continue;
			u.insert(mkp(col[i], col[j]));
			_add(col[i], col[j]);
			add_(col[j], col[i]);
		}
	}
	SPFA1(col[1]), SPFA2(col[1]);
	res = siz[col[1]];
	for (int i = 1; i <= cntw; ++i) {
		for (auto j : g1[i])
			res = max(res, d1[j] + d2[i]);
	}
	print(res);
	return 0;
}
} // namespace XSC062

G. Tourist Reform

http://222.180.160.110:1024/contest/3698/problem/7

想到一半想不下去了，想着看看 tj 前两排拿点思路吧，结果 tj 前两排就是我已经想到的所有内容。于是我又往下看了一排，好家伙，直接把分化点给我摆出来了……

先尝试求解出最小 \(r_i\) 的值。

我们都知道，边双在执行有向化操作（暂且这么称呼）后一定可以变成强连通分量。

把原图按边双缩点之后会成为一棵树，我们需要把树上的所有边有向化以达到最大收益。

这里有一个分化点，

标签：连通,return,int,230623,read,dfn,maxn,low,分量
From： https://www.cnblogs.com/XSC062/p/17498727.html

相关文章

  • 1595. 连通两组点的最小成本 (Hard)
    问题描述1595.连通两组点的最小成本(Hard)给你两组点，其中第一组中有size₁个点，第二组中有size₂个点，且size₁>=size₂。任意两点间的连接成本cost由大小为size₁xsize₂矩阵给出，其中cost[i][j]是第一组中的点i和第二组中的点j的连接成本。如果两个组中......
  • 1595. 连通两组点的最小成本
    给你两组点，其中第一组中有size1个点，第二组中有size2个点，且size1>=size2。任意两点间的连接成本cost由大小为size1xsize2矩阵给出，其中cost[i][j]是第一组中的点i和第二组中的点j的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点......
  • 连通两组点的最小成本
    如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的返回连通两组点所需的最小成本1.状态压缩+动态规划classSolution{public:intconnectTwoGroups(vector<vector<int>>&cost){//这里使用状态压缩记录连通状态，同时使用动态规划最......
  • POJ2117 Electricity 题解 tarjan点双连通分量 割点
    题目链接：http://poj.org/problem?id=2117题目大意：给定一个由\(n\)个点\(m\)解题思路：tarjan，判断\(u\)的子节点有几个\(v\)满足\(low[v]\gedfn[u]\)就是答案，但是同时如果\(u\)不是这个dfs树的根节点，个数还要加\(1\)。示例程序1（C++11，POJ不支持）：#include<bits/stdc++.h>......
  • P2860 [USACO06JAN]Redundant Paths G 题解 tarjan边双连通分量
    题目链接：https://www.luogu.com.cn/problem/P2860题目大意：给定一个无向连通图，求至少加几条边，能使其变成一个边双连通图。解题思路：边双连通分量缩点后计算度数为\(1\)的节点个数，假设有\(cnt\)个，则答案为\((cnt+1)/2\)。示例程序：#include<bits/stdc++.h>usingnamespacestd;......
  • CF402E Strictly Positive Matrix 题解 tarjan强连通分量
    题目链接：http://codeforces.com/problemset/problem/402/E题目大意：给出一个矩阵\(A\)，问是否存在一个正整数\(k\)使得\(A^k\)解题思路：根据矩阵的性质，\(A^k_{i,j}\gt0\)当且仅当\(i\)到\(j\)所以可以把矩阵转成图论模型，若\(A_{i,j}\gt0\)，则从\(i\)往\(j\)如果所有点......
  • POJ2117 Electricity 题解 tarjan点双连通分量 割点
    题目链接：http://poj.org/problem?id=2117题目大意：给定一个由\(n\)个点\(m\)条边构成的无向图，请你求出该图删除一个点之后，连通块最多有多少。解题思路：tarjan，判断\(u\)的子节点有几个\(v\)满足\(low[v]\gedfn[u]\)就是答案，但是同时如果\(u\)不是这个dfs树的根节......
  • P2860 [USACO06JAN]Redundant Paths G 题解 ratjan边双连通分量
    题目链接：https://www.luogu.com.cn/problem/P2860题目大意：给定一个无向连通图，求至少加几条边，能使其变成一个边双连通图。解题思路：边双连通分量缩点后计算度数为\(1\)的节点个数，假设有\(cnt\)个，则答案为\((cnt+1)/2\)。示例程序：#include<bits/stdc++.h>usingnamespac......
  • 数据结构与算法分析（Java语言描述）（27）—— 深度优先遍历与连通分量
    packagecom.dataStructure.graph;//求无权图的联通分量publicclassComponents{privateGraphgraph;//存放输入的数组privateboolean[]visited;//存放节点被访问状态privateintcomponentCount;//连通分量的数量privateint[]mark;//......
  • 图像连通域
    四连通和八连通域label,num=measure.label(mask_img,neighbors=8,background=0,return_num=True)参考:[1]https://blog.csdn.net/weixin_39976081/article/details/112069671[2]https://scikit-image.org/docs/dev/api/skimage.measure.html#skimage.measure.label[3......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99