强连通分量+缩点

lc3383

强连通分量：图里互相可达的节点，打包成一个整体。
缩点：把每个强连通分量当成一个“超级节点”，原图变成有向无环图

#include <vector>
using namespace std;

class Solution {
public:
int minRunesToAdd(int n, vector<int>& crystals, vector<int>& flowFrom, vector<int>& flowTo) {
vector<vector<int>> g(n);
vector<vector<int>> rg(n);

for (int i = 0; i < flowFrom.size(); ++i) {
int u = flowFrom[i], v = flowTo[i];
g[u].push_back(v);
rg[v].push_back(u);
}

vector<bool> vis(n), vis2(n);

auto dfs = [&](auto&& self, int x) -> void {
if (vis[x]) return;
vis[x] = 1;
for (int y : g[x]) self(self, y);
};

auto dfs2 = [&](auto&& self, int x) -> bool {
if (!vis[x]) return 1;
if (vis2[x]) return 0;
vis2[x] = 1;
for (int y : rg[x]) if (self(self, y)) return 1;
return 0;
};

for (int c : crystals) dfs(dfs, c);

int ret = 0;
for (int i = 0; i < n; ++i) {
if (!vis[i]) {
dfs(dfs, i);
if (!dfs2(dfs2, i)) ret++;
}
}
return ret;
}
};