526互联

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

发布时间 2023-06-23 11:02:25作者: XSC062

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

原曲：花与树的女儿们

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\) 的值。

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

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

这里有一个分化点，