[Tarjan] 学习笔记
原理
强连通分量
讲得超级屌，这次比董晓好得多
强连通：在有向图中，两点能互相到达；
强连通分量：在有向图中，有一种子图，子图里所有点都强连通，特别地，单点也被认为是强连通分量；
void tarjan(int x)
{
dfn[x] = low[x] = t ++;
s.push(x);
in[x] = true;
for (int i = h[x]; i ; i = e[i].next)
{
int y = e[i].to;
if (!dfn[y])
{
tarjan(y);
low[x] = min(low[x], low[y]);
}
else if (in[y])
low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x])
{
while (s.top() != x)
{
in[s.top()] = false;
cout << s.top() << ' ';
s.pop();
}
in[s.top()] = false;
cout << s.top() << '\n';
s.pop();
}
}