题意
强连通缩点 算法
Kosaraju 算法
首先,我们对图进行 DFS,按 DFS 中返回的顺序编号,如图
然后,我们将所有的边 反向,如图
接下来,按顶点编号 从大到小,再进行搜索,搜到的连通块,就是 一个强连通分量。
比如,在搜索编号为 $10$ 的顶点时,搜到了 $8\ 9\ 10$,所以 $8, 9, 10$ 这三个点是 一个强连通分量。
搜完之后的结果:
正确性
在 Kosaraju 算法中,先将有向图 $G$ 的边反向得到 $G'$,然后计算 $G'$ 的拓扑序 $ord$,然后再将 $G$ 按照 $ord$ 的顺序进行 DFS。
- 对 $G$ 进行 DFS,出现从 $x$ 递归到 $y$ 的情况,说明在 $G$ 中存在一条有向边 $x \to y$。
- 在 $ord$ 中,只有 $x$ 在 $y$ 前面的情况下,才可能出现从 $x$ 递归到 $y$ 的情况。
- 如果存在 $x \to y$,那么在 $ord$ 中,$y$ 一定在 $x$ 前面。
- 如果拓扑序是 $x$ 在 $y$ 前面,又存在 $y \to x$,那么 $x \to y$ 也成立。即 $x$ 和 $y$ 在一个强连通分量中。
代码
// By rbtree (https://rbtr.ee) :\
// Please submit with C++14!
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <valarray>
#include <vector>
#define ra _Read_Int()
#define rc _Read_Char()
#define rs _Read_String()
#define rr _READ_RAW_::_Rd()
#define iotop _Get_IO_Top()
#define __FAST__ 1
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#define dputs(...)
#endif
using tp = long long;
tp _Read_Int();
char _Read_Char();
char _Get_IO_Top();
std::string _Read_String();
namespace _READ_RAW_ {
char _Rd();
} // namespace _READ_RAW_
using namespace std;
constexpr bool __MTCS__ = 0;
constexpr tp _BUF_SIZE_ = 217'217'21;
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
namespace __SOL__ {
constexpr tp Hat_N = 10003, Hat_M = 1e5 + 3;
bool vis[Hat_N];
tp w[Hat_N], sccno[Hat_N], f[Hat_N], sccw[Hat_N], u[Hat_M], v[Hat_M];
list<tp> stk, g[Hat_N], fg[Hat_N];
tp n, cnt;
void dfs(tp x) {
if (vis[x]) {
return;
}
vis[x] = 1;
for (auto&& i : g[x]) {
dfs(i);
}
stk.push_back(x);
}
void mark(tp x, tp f) {
sccno[x] = f;
sccw[f] += w[x];
for (auto&& i : fg[x]) {
if (!sccno[i]) {
mark(i, f);
}
}
}
void kosaraju() {
for (tp i = 1; i <= n; ++i) {
dfs(i);
}
while (stk.size()) {
if (!sccno[stk.back()]) {
mark(stk.back(), ++cnt);
}
stk.pop_back();
}
}
void dp(tp x) {
if (f[x]) {
return;
}
for (auto&& i : g[x]) {
dp(i);
f[x] = max(f[x], f[i]);
}
f[x] += sccw[x];
}
void main([[maybe_unused]] size_t __CASE__) { // :/
n = ra;
tp m = ra, tar = 0;
for (tp i = 1; i <= n; ++i) {
w[i] = ra;
}
for (tp i = 0; i < m; ++i) {
u[i] = ra;
v[i] = ra;
g[u[i]].push_back(v[i]);
fg[v[i]].push_back(u[i]);
}
kosaraju();
for (tp i = 1; i <= n; ++i) {
g[i].clear();
}
for (tp i = 0; i < m; ++i) {
if (sccno[u[i]] != sccno[v[i]]) {
g[sccno[u[i]]].push_back(sccno[v[i]]);
}
}
for (tp i = 1; i <= cnt; ++i) {
dp(i);
tar = max(tar, f[i]);
}
printf("%lld\n", tar);
} // :)
} // namespace __SOL__
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
signed main() {
tp __MTCS__ = ::__MTCS__ ? ra : 1;
for (tp __i = 1; __i <= __MTCS__; ++__i) {
__SOL__::main(__i);
}
return EXIT_SUCCESS;
}
namespace _READ_RAW_ {
#if __FAST__
std::array<char, _BUF_SIZE_ + 1> _BUF_;
std::array<char, _BUF_SIZE_>::iterator __Cur = _BUF_.begin(), __End = __Cur + 1;
char _Rd() {
if (++__Cur == __End) {
__Cur = _BUF_.begin();
__End = __Cur + fread(_BUF_.begin(), 1, _BUF_SIZE_, stdin);
*__End++ = 10;
}
return *__Cur;
}
} // namespace _READ_RAW_
char _Get_IO_Top() {
if (_READ_RAW_::__Cur + 1 == _READ_RAW_::__End) {
_READ_RAW_::__Cur = _READ_RAW_::_BUF_.begin();
_READ_RAW_::__End = _READ_RAW_::__Cur +
fread(_READ_RAW_::_BUF_.begin(), 1, _BUF_SIZE_, stdin);
if (_READ_RAW_::__Cur == _READ_RAW_::__End) {
return --_READ_RAW_::__Cur, -1;
} else {
return *_READ_RAW_::__Cur--;
}
}
return *(_READ_RAW_::__Cur + 1);
#else
char _Rd() {
return getchar();
}
#endif
} // namespace _READ_RAW_
tp _Read_Int() {
bool __neg(0);
char __c(_READ_RAW_::_Rd());
tp __val;
for (; __c < 48 || __c > 57; __c = _READ_RAW_::_Rd()) {
__neg = __c == 45;
}
__val = __c & 15;
for (__c = _READ_RAW_::_Rd(); __c > 47 && __c < 58; __c = _READ_RAW_::_Rd()) {
__val = __val * 10 + (__c & 15);
}
return __neg ? ~__val + 1 : __val;
}
char _Read_Char() {
char __c(_READ_RAW_::_Rd());
for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
}
return __c;
}
std::string _Read_String() {
char __c(_READ_RAW_::_Rd());
std::string __val;
for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
}
do {
__val.push_back(__c);
__c = _READ_RAW_::_Rd();
} while (__c != 32 && __c != 10 && __c != 13);
return __val;
}
//\
___ ___ ___________ \
|\ \ |\ \ |\ ___ \
\ \ \ \ \ \ \ \ \|_\ \
\ \ \ __\ \ \ \ \ ___ \
\ \ \|\__\_\ \ \ \ \ \ \
\ \____________\ \ \___\ \___\
\|____________| \|___| |___|
/*#################################################################
#.................................................................#
#............................This.Code.Was.Created.By.RBTree......#
#.............#......#...............Limiting-Factor..............#
#............#.#....#.#.................Soul-Code.................#
#.............########............................................#
#............#........#..##############################...........#
#...........#..V....V......#..#........................#..#...#...#
#............#........#....#..........###..###..........#..#.#.#..#
#............#..X##X..#..#............#....#.#...........#..#...#.#
#...........#...N##N...#..#...........###..###..........#.........#
#.......MOE..#..@.....#....#.#.#.#...................#.#..........#
#.............########.....#.#.#.##############.#.#..#.#..........#
#..........................#.#.#.#.............#.#.#.#.#..........#
#......#########...........#.#.#.#.................#.#.#..........#
#.....#.........#..........#.#.#.#.................#.#.#..........#
#.#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/
Tarjan 算法
以后有空写