可能是一种新的求边所在点双的方式
粥2414
·
·
算法·理论
先叠个甲，网上很少有专门讲求边所在点双的，我无法保证我是第一个发现这种算法的，但是我可以保证我是独立发现它的，巨佬勿喷。
做法
设 bel_i 表示边 i 所属点双，del_j 表示点 j 所属点双编号最大的那个，那么对于任意一条边，设其两端为 u,v，那么有：
bel_i=\min(del_u,del_v)
证明
首先要明确以下几点：
- 边一定且只能属于一个点双。
- 边两端点一定属于一个点双。
- 非割点只属于一个点双，对于割点，认为它同时属于多个点双。
- 正常 tarjan 算法先判定出的点双编号小。
分三种情况证明。
情况 1
那么这两点显然一定属于同一个点双，所以上式显然正确。
### 情况 $2
此时 $u$ 可能属于多个点双，我们只需证明一定有 $del_v\leq del_u$ 即可。
那么很显然，更新 $del_v$ 的时候一定会更新 $del_u$，那么如果后面有新的点双包括 $u$，$del_v$ 一定小于 $del_u$。所以上式成立。
### 情况 $3
我们设 $u$ 为 $v$ 的子孙。那么最后一个包含 $u$ 的点双一定包含 $u$ 和 $u$ 的祖先，当然也包括这条边。这是因为在 tarjan 中是从下往上判定点双的。且此时一定会更新 $v$ 所在的点双。那么上式就显然了。
如果有巨佬发现证明过程中有疏漏或者错误，请及时指出，蒟蒻一定会改正。
# 代码实现
只需要对 tarjan 进行一点小小的改动即可。
```cpp
//tarjan
int dfn[N], low[N];
int dcnt, scnt;
vector<int>scc[N];//点双不是强连通分量
stack<int>s;
int root;
int bel[N], del[N];
void tarjan(int now, int fa) {
dfn[now] = low[now] = ++dcnt;
s.push(now);
for (int i = h[now]; i; i = lian[i].ne) {//链式前向星
int to = lian[i].to;
if (!dfn[to]) {
tarjan(to, i);
low[now] = min(low[now], low[to]);
if (low[to] >= dfn[now]) {
scnt++;
while (s.top() != to) {
scc[scnt].push_back(s.top());
del[s.top()] = scnt;
s.pop();
}
scc[scnt].push_back(s.top());
del[s.top()] = scnt;
s.pop();
scc[scnt].push_back(now);
del[now] = scnt;//新的一定是更大的，直接赋值即可
}
} else low[now] = min(low[now], dfn[to]);
}
if (now == root)
s.pop();
}
void solve() {
for (int i = 1; i < N; i++) {
for (int j = h[i]; j; j = lian[j].ne)
bel[lian[j].id] = min(del[i], del[lian[j].to]);//取较小值即可
}
}
```
# 其他方法
目前我所了解的求边所在点双的方法有以下两种：
1. [这篇题解](https://www.luogu.com.cn/article/s7x8nipf)的写法，将边入栈而不是让点入栈。
2. [这篇题解](https://www.luogu.com.cn/article/qrkjsm2p)的方法，先建出圆方树，然后进行分类讨论。
其实细想我的方法和这几种方法没有本质区别，且可以相互转化。