题解：P5234 [JSOI2012] 越狱老虎桥
提供一个自认为很简便的做法，核心算法只用到了边双缩点。
模板链接：P8436 【模板】边双连通分量。
思路
首先注意到一个很显然的，如果一条边属于一个环，那么摧毁无效，所以可以先缩点，然后建立一颗新树。
然后考虑以一号节点为根跑出这棵树，注意这时一号节点下标是
考虑新增一条边，本质上其实可以拆成两条链，考虑维护这两条链，我们可以对于每个点求出 DFS 序和子树大小，然后根据 DFS 序的经典结论，
- 属于第一条链，即看是否可以当开头和结尾，注意，如果有第二条链，然后这个点为两条链顶的公共祖先，那么就不合法，否则看是否是开头的后代且是结尾的祖先，就是在这个链里面，就可以不用管。
- 属于第二条链，同理。
- 没有第一条链，自己作为第一条链。
- 没有第二条链，看自己是否是第一条连开头的后代，如果是就不行，因为如果以它为第二条链，那么就覆盖不了开头的那个点了。
然后就没了，复杂度瓶颈在于排序，随便优化一下就可以线性了，稍微优化一下就能做到当前最优解第一。
#include<bits/stdc++.h>
using namespace std;
#define getchar() (p1 == p2 && (p2 = (p1 = buf1) + fread(buf1, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf1[1 << 23], *p1 = buf1, *p2 = buf1, ubuf[1 << 23], *u = ubuf;
namespace IO
{
template<typename T>
void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
template<typename T,typename... Args>
void read(T &_x,Args&...others){Read(_x);Read(others...);}
const int BUF=20000000;char buf[BUF],to,stk[32];int plen;
#define pc(x) buf[plen++]=x
#define flush(); fwrite(buf,1,plen,stdout),plen=0;
template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++to]=48+x%10;while(to) pc(stk[to--]);}
}
using namespace IO;
const int N = 1e6+10,V = 1e5;
int n,m,x,y,z,head[N],cnt,low[N],dep[N],t[N],col[N],o;
int fa[N],dfn[N],siz[N],cnt1;//求出dfn与fa
int L,R,L1,R1;//两条链
struct w1
{
int x,y;
}ed[N];
vector<int>v[V+10];
struct w
{
int to,nxt;
}b[N<<1];
inline void add(int x,int y)
{
b[++cnt].nxt = head[x];
b[cnt].to = y;
head[x] = cnt;
}
void dfs(int x,int y)
{
dep[x] = low[x] = dep[y]+1; t[++cnt] = x;
for(int i = head[x];i;i = b[i].nxt)
{
if(b[i].to == y) continue;
if(!dep[b[i].to]) dfs(b[i].to,x),low[x] = min(low[x],low[b[i].to]);
else low[x] = min(low[x],dep[b[i].to]);
}
if(dep[x] == low[x])
{
o++;
while(t[cnt+1] != x) col[t[cnt]] = o,cnt--;
}
}
void dfs1(int x,int y)
{
fa[x] = y,siz[x] = 1,dfn[x] = ++cnt1;
for(int i = head[x];i;i = b[i].nxt)
if(b[i].to != y)
dfs1(b[i].to,x),siz[x] += siz[b[i].to];
}
signed main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n),read(m);
for(int i = 1;i <= m;i++) read(x),read(y),read(z),add(x,y),add(y,x),ed[i].x = x,ed[i].y = y,v[z].push_back(i);
cnt = 0; dfs(1,0);//注意处理之前要清空
for(int i = 1;i <= n;i++) head[i] = 0;
for(int i = 1;i <= m;i++) ed[i].x = col[ed[i].x],ed[i].y = col[ed[i].y];
for(int i = 1;i <= m;i++)
if(ed[i].x != ed[i].y)
add(ed[i].x,ed[i].y),add(ed[i].y,ed[i].x);
dfs1(col[1],0);//注意到根节点是col_1
for(int j = 1;j <= V;j++)
for(int z = 0;z < v[j].size();z++)
{
int i = v[j][z];
x = ed[i].x,y = ed[i].y;
if(x != y)
{
if(fa[x] == y) swap(x,y);
//默认x是y父亲
if(L == 0) L = R = y;//没有就放上，注意链化点是下面的点
else
{
if(dfn[R] <= dfn[y] && dfn[y] <= dfn[R]+siz[R]-1) R = y; //尾部
else if(L && L1 && dfn[y] <= min(dfn[L],dfn[L1]) && max(dfn[L],dfn[L1]) <= dfn[y]+siz[y]-1)//无法放置
{
print(j); flush();
return 0;
}
else if(dfn[y] <= dfn[L] && dfn[L] <= dfn[y]+siz[y]-1) L = y;//链头
else if(dfn[L] <= dfn[y] && dfn[y] <= dfn[L]+siz[L]-1 && dfn[y] <= dfn[R] && dfn[R] <= dfn[y]+siz[y]-1);
else
{
if(L1 == 0)
{
if(dfn[L] <= dfn[y] && dfn[y] <= dfn[L]+siz[L]-1)//无法放置
{
print(j); flush();
return 0;
}
L1 = R1 = y;
}
else if(dfn[R1] <= dfn[y] && dfn[y] <= dfn[R1]+siz[R1]-1) R1 = y; //尾部
else if(dfn[y] <= dfn[L1] && dfn[L1] <= dfn[y]+siz[y]-1) L1 = y;//链头
else if(dfn[L1] <= dfn[y] && dfn[y] <= dfn[L1]+siz[L]-1 && dfn[y] <= dfn[R1] && dfn[R1] <= dfn[y]+siz[y]-1);
else { print(j); flush(); return 0; }
}
}
}
}
print(-1); flush();
return 0;
}
/*
先枚举选哪条边
然后如果对应的点在一个边双内，就不管
否则看我有没有放秘密的线
考虑染色，如果第一次出现两个不同链，就是边的链接之日
然后继续走知道非这两条链上的同时也不是边双的
其实不妨可以理解为两次链接根的机会
不过链尾不知道是哪一个
可以搞两个L,R, L1,R1
分别是两条链的头与尾
如果被L包含了，且不包含R，立即结束
到最后都没结束的话...【我们需要帮助】
*/