邊雙連通分量(一般配上縮點、并查集)
tot = 1;
void add(int x,int y)
{
nextt[++tot] = head[x];
head[x] = tot;
to[tot] = y;
from[tot] = x;
}
void tarjan(int u)
{
pre[u] = low[u] = ++dfs_clock;
for (int i = head[u];i;i = nextt[i])
{
if (i == (bian[u] ^ 1))
continue;
int v = to[i];
if (!pre[v])
{
bian[v] = i;
tarjan(v);
if (low[v] < low[u])
low[u] = low[v];
if (low[v] > pre[u])
flag[bian[v]] = flag[bian[v] ^ 1] = 1;
}
else
if (pre[v] < low[u])
low[u] = pre[v];
}
}
int find(int x)
{
if (x == fa[x])
return x;
return fa[x] = find(fa[x]);
}
for (int i = 2; i <= tot; i += 2)
if (!flag[i])
fa[find(to[i])] = find(from[i]);
void dfs(int u,int fa)
{
pre[u] = low[u] = ++dfs_clock;
int child = 0;
for (int i = head[u];i;i = nextt[i])
{
int v = to[i];
if (!pre[v])
{
node temp;
temp.u = u;
temp.v = v;
e[++top] = temp;
child++;
dfs(v,u);
low[u] = min(low[u],low[v]);
if (low[v] >= pre[u])
{
iscut[u] = 1;
num++;
while (1)
{
int tu = e[top].u,tv = e[top--].v;
if (belong[tu] != num)
belong[tu] = num;
if (belong[tv] != num)
belong[tv] = num;
if (tu == u && tv == v)
break;
}
}
}
else
if (pre[v] < pre[u] && v != fa)
{
node temp;
temp.u = u;
temp.v = v;
e[++top] = temp;
low[u] = min(low[u],pre[v]);
}
}
if (child == 1 && fa == -1)
iscut[u] = 0;
}