题解 P2783 【有机化学之神偶尔会做作弊】
钱逸凡
2018-11-08 12:35:51
又一道~~水~~黑题
# 思路：
## 显然的缩点+树剖/倍增求lca
由于是无向图，缩点时写法略有变化，即一个点和他的父亲不能构成强连通分量
缩点就这么写：~~（码风略丑）~~
```
void dfs(int u,int fa){
vis[u]=1;
dfn[u]=low[u]=++ti;
st[++sttop]=u;
inst[u]=1;
for(int i=oldhead[u];i;i=nod[i].next){
int d=nod[i].v;
if(d==fa)continue;
if(!vis[d]){
dfs(d,u);
low[u]=min(low[u],low[d]);
}
else if(inst[d])low[u]=min(low[d],low[u]);
}
if(dfn[u]==low[u]){
int now;
taj++;
do{
now=st[sttop--];
inst[now]=0;
Belong[now]=taj;
}while(now!=u);
}
}
```
还有这奇怪的输出格式：
```
inline int out(int n){//输出n的二进制表示
int o=log2(n);
for(;o>=0;o--){
if((1<<o)<=n){
n-=(1<<o);
printf("1");
}
else printf("0");
}
printf("\n");
}
```
------------
完整代码：
```
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
inline int Read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
int toop,cnt;
int oldhead[11010];
int head[10101];
struct Node{
int v;
int next;
}nod[101010],node[101010];
inline void ad(int u,int v){
nod[++toop].v=v;
nod[toop].next=oldhead[u];
oldhead[u]=toop;
}//旧图
inline void addedge(int u,int v){
node[++cnt].v=v;
node[cnt].next=head[u];
head[u]=cnt;
}//新图
inline void add(int u,int v){
ad(u,v);
ad(v,u);
}//旧图
inline void newadd(int u,int v){
addedge(u,v);
addedge(v,u);
}//新图
int n,m;
int Belong[11010];
int vis[11010];
bool inst[10505];
int st[10101];
int sttop;
int taj;
int dfn[10101],low[10101],ti;
void dfs(int u,int fa){
vis[u]=1;
dfn[u]=low[u]=++ti;
st[++sttop]=u;
inst[u]=1;
for(int i=oldhead[u];i;i=nod[i].next){
int d=nod[i].v;
if(d==fa)continue;
if(!vis[d]){
dfs(d,u);
low[u]=min(low[u],low[d]);
}
else if(inst[d])low[u]=min(low[d],low[u]);
}
if(dfn[u]==low[u]){
int now;
taj++;
do{
now=st[sttop--];
inst[now]=0;
Belong[now]=taj;
}while(now!=u);
}
}
void sd(){
int i,j;
for(i=1;i<=n;i++)if(!vis[i])dfs(i,i);
for(i=1;i<=n;i++){
for(j=oldhead[i];j;j=nod[j].next){
int d=nod[j].v;
if(Belong[i]!=Belong[d]) newadd(Belong[i],Belong[d]);
}
}
}
int dep[10101],siz[10101],fa[10101],son[10101],top[10101];
void dfs1(int u){
siz[u]=1;
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(fa[u]!=d){
fa[d]=u;
dep[d]=dep[u]+1;
dfs1(d);
siz[u]+=siz[d];
if(siz[d]>siz[son[u]])son[u]=d;
}
}
}
void dfs2(int u,int tp){
top[u]=tp;
if(son[u])dfs2(son[u],tp);
for(int i=head[u];i;i=node[i].next){
int d=node[i].v;
if(fa[u]!=d&&son[u]!=d)dfs2(d,d);
}
}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]])u=fa[top[u]];
else v=fa[top[v]];
}
return dep[u]>dep[v]?v:u;
}
inline int out(int n){
int o=log2(n);
for(;o>=0;o--){
if((1<<o)<=n){
n-=(1<<o);
printf("1");
}
else printf("0");
}
printf("\n");
}
int main(){
n=Read(),m=Read();
register int i;
int u,v;
for(i=1;i<=m;i++)u=Read(),v=Read(),ad(u,v);
sd();
dep[1]=1;
dfs1(1);
dfs2(1,1);
int q;
q=Read();
while(q--){
u=Read(),v=Read();
u=Belong[u];
v=Belong[v];
out(dep[u]+dep[v]-2*dep[lca(u,v)]+1);
}
return 0;
}
```
# ~~求赞~~