[ARC143D] Bridges
题意：给定 \(2n\) 个点和 \((u_1,v_1) , \cdots , (u_m,v_m)\)，选择让 \(u_i\) 连 \(v_i+n\) 或 \(v_i\) 连 \(u_i+n\)，以最小化图中桥的个数。
有种技巧叫拆点，把一个点拆成入点和出点，看这个形式非常像拆点，于是先想想合并。
若有 \(n\) 个点，连上所有 \(u_i\) 和 \(v_i\)，是桥的边在原图中只能是桥（路径唯一），抛出结论：可以通过构造，让其他边均不是桥。
如果现在在看一个连通块，只需要通过把边重定向以使得这一块强连通，即可。
考虑去掉那些桥后一个一个连通块处理：顺着 DFS 树走下去，遇到返祖边向上定向，否则向下定向，即得。
以前听说过拆点这个想法，但这是第一次见到，甚至连可以合并两个点都没想到，只能说是发散思维的极大不足了。确实想到了某种 \(i\) 与 \(i+n\) 间奇怪的对应关系，但“桥”导致往 tarjan 上想，这是复杂化了问题。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e6+100;
struct node{
int to,next;
}e[N];
int n,m,cnt=1;
int a[N],b[N],head[N],dir[N];
bool vis[N],vis1[N];
void add(int x,int y){
e[++cnt]={y,head[x]};
head[x]=cnt;
}
void dfs(int now,int fa){
if(vis1[now]) return ;
vis1[now]=1;
for(int i=head[now];i;i=e[i].next){
int v=e[i].to;
if((i^1)==fa||vis[i]) continue;
vis[i^1]=vis[i]=1;
dir[i]=1;
dir[i^1]=0;
dfs(v,i);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>b[i];
for(int i=1;i<=m;i++) add(a[i],b[i]),add(b[i],a[i]);
for(int i=1;i<=n;i++) if(!vis1[i]) dfs(i,0);
for(int i=1;i<=m;i++) cout<<dir[i<<1];
return 0;
}