翻译
给你一张N个点M条边且边权均为1的图
Q次询问两点之间的最短路
性质：
如果图中有环 这个环上的点构成的子图一定是一个完全子图
题解
如果有环那么显然环上任意两点的距离都是1
建出圆方树
数一下两点路径上圆点个数+方点个数
乱撸一下…
其实只是来扔板子的
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #define LL long long #define mp(x,y) make_pair(x,y) using namespace std; inline int read() {
int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}return x*f; } inline void write(int x) {
if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0'); } inline void print(int x){
write(x);puts("");} struct node{
int x,y,c,next;}a[3110000],b[3110000];int len1,last1[1111000],len2,last2[1111000]; void ins_a(int x,int y){
len1++;a[len1].x=x;a[len1].y=y;a[len1].next=last1[x];last1[x]=len1;} void ins_b(int x,int y,int c){
len2++;b[len2].x=x;b[len2].y=y;b[len2].c=c;b[len2].next=last2[x];last2[x]=len2;} int low[410000],dfn[410000],sta[410000],tp,id,cnt; int r[410000]; void link() {
for(int i=2;i<=r[0];i++)ins_b(cnt,r[i],0),ins_b(r[i],cnt,0);ins_b(r[1],cnt,1);ins_b(cnt,r[1],1); } void tarjan(int x,int fa) {
low[x]=dfn[x]=++id;sta[++tp]=x;for(int k=last1[x];k;k=a[k].next)if(a[k].y!=fa){
int y=a[k].y;if(dfn[y]==-1){
tarjan(y,x);low[x]=min(low[x],low[y]);if(low[y]>dfn[x])ins_b(x,y,1),ins_b(y,x,1),tp--;else if(low[y]==dfn[x]){
cnt++;r[r[0]=1]=x;int i;do{
i=sta[tp--];r[++r[0]]=i;}while(i!=y);link();}}else low[x]=min(low[x],dfn[y]);} } int bin[25],fa[611000][25],sum[611000][25],dep[811000]; void pre_tree_node(int x) {
for(int i=1;bin[i]<=dep[x];i++)fa[x][i]=fa[fa[x][i-1]][i-1],sum[x][i]=sum[x][i-1]+sum[fa[x][i-1]][i-1];for(int k=last2[x];k;k=b[k].next){
int y=b[k].y;if(y!=fa[x][0]){
fa[y][0]=x;dep[y]=dep[x]+1;sum[y][0]=b[k].c;pre_tree_node(y);}} } int pa; int lca(int x,int y) {
pa=0;if(dep[x]<dep[y])swap(x,y);for(int i=20;i>=0;i--)if(bin[i]<=dep[x]&&dep[fa[x][i]]>=dep[y])pa+=sum[x][i],x=fa[x][i];if(x==y)return x;for(int i=20;i>=0;i--)if(bin[i]<=dep[x]&&fa[x][i]!=fa[y][i])pa+=sum[x][i]+sum[y][i],x=fa[x][i],y=fa[y][i];pa+=sum[x][0]+sum[y][0];return fa[x][0]; } int up(int x,int p) {
for(int i=20;i>=0;i--)if(bin[i]<=p)p-=bin[i],x=fa[x][i];return x; } int n,m,Q; int main() {
bin[0]=1;for(int i=1;i<=20;i++)bin[i]=bin[i-1]<<1;n=read();m=read();Q=read();for(int i=1;i<=m;i++){
int x=read(),y=read();ins_a(x,y);ins_a(y,x);}cnt=n;memset(dfn,-1,sizeof(dfn));for(int i=1;i<=n;i++)if(dfn[i]==-1)tarjan(i,0);for(int i=1;i<=n;i++)if(dep[i]==0)pre_tree_node(i);while(Q--){
int x=read(),y=read();int LA=lca(x,y);if(LA<=n)print(pa);else{
int u=up(x,dep[x]-dep[LA]-1),v=up(y,dep[y]-dep[LA]-1);if(!sum[u][0]&&!sum[v][0])pa++;print(pa);}}return 0; }