给定一个有向图,每个点的出度都为1,稍微画一下就知道图的特征:一个森林,森林中每个树都含有一个有向环,环上挂着很多有向树。问题是询问两个点的最短距离。
三种情况:
1:两个点在两个子图中
2:两个点在一个子图中,但是不在一个子树上(暂且叫子树吧)
3:两个点在一个子图中,且在同一个子树上
观察图的形态,由于n个点n条边,且每个点出度为1,因此可以认为是一个森林,森林里每棵树都加了一条边形成了一个环,且环是根节点(可以认为缩点后没有出边,即没有父节点)。
显然两点属于不同树的时候不可达;因为图的特殊性,因此没有用强连通做,而是用了并查集判环,也便于给环上每个点标上相对位置。
如果两点在同一颗树上,如果不在根节点的同一分支,那么他们首先要走到环上,然后一个人不动另一个走(至于让a走还是b走要根据两点在环上的相对位置判断优弧和劣弧),如果在同一分支,那就是普通的树上两点间的路径。
如果没有那个环,那就是一个普通的森林中的LCA问题,但是由于缩点了,因此要增加一个虚拟根节点0,把所有环上的点可做是森林中子树的根节点,虚拟根节点向所有树的根节点连边,然后做LCA,如果发现ab两点之间LCA为0,则判断两点是否在一颗子树中,如果不在和不可达,如果在则判优弧和劣弧;如果不等于0,那就等同于一棵树的LCA,可以直接确定两点间的最短距离。
#include <iostream> #include <vector> #include <cmath> #include <cstdio> using namespace std; struct node{ int x,y; node(){} node(int _x,int _y):x(_x),y(_y){} }; struct NODE{ int set[500010]; void init(int n){ int i; for(i=1;i<=n;i++) set[i]=i; } int find(int x){ if(set[x]!=x) set[x]=find(set[x]); return set[x]; } }; const int N=500010; NODE a,b; int n,m,pre[N],root[N],dep[N],lca[N],circle[N]; vector<int> edges[N]; vector<node> query[N]; int isroot[N],x[N],y[N]; int visit[N],flag[N]; void InPut(){ int i,p,q; a.init(n); for(i=1;i<=n;i++){ edges[i].clear(); query[i].clear(); } for(i=1;i<=n;i++){ scanf("%d",&pre[i]); edges[pre[i]].push_back(i); p=a.find(i); q=a.find(pre[i]); a.set[p]=q; } for(i=0;i<m;i++){ scanf("%d%d",&x[i],&y[i]); query[x[i]].push_back(node(y[i],i)); query[y[i]].push_back(node(x[i],i)); } } void DFS(int u,int depth,int Root){ int i,v,x,y; dep[u]=depth; root[u]=Root; for(i=0;i<edges[u].size();i++){ v=edges[u][i]; if(isroot[v]!=-1||v==u) continue; DFS(v,depth+1,Root); b.set[v]=u; } visit[u]=1; for(i=0;i<query[u].size();i++) { x=query[u][i].x; y=query[u][i].y; if(visit[x]&&root[u]==root[x]) lca[y]=b.find(x); } } void OutPut() { int i,k,u,v,rootX,rootY,size,X,Y,A,B; for(i=0;i<m;i++) { if(a.find(x[i])!=a.find(y[i])) { puts("-1 -1"); continue; } if(root[x[i]]==root[y[i]]) { k=lca[i]; printf("%d %d\n",dep[x[i]]-dep[k],dep[y[i]]-dep[k]); continue; } u=dep[x[i]]; v=dep[y[i]]; rootX=root[x[i]]; rootY=root[y[i]]; size=circle[a.find(rootX)]; X=(isroot[rootY]-isroot[rootX]+size)%size; Y=(isroot[rootX]-isroot[rootY]+size)%size; if(max(u+X,v)<max(u,v+Y)) A=u+X,B=v; else if(max(u+X,v)>max(u,v+Y)) A=u,B=v+Y; else if(min(u+X,v)<min(u,v+Y)) A=u+X,B=v; else if(min(u+X,v)>min(u,v+Y)) A=u,B=v+Y; else A=u+X,B=v; printf("%d %d\n",A,B); } } int main(){ while(scanf("%d%d",&n,&m)!=-1) { InPut(); int i,j,k,num; memset(isroot,-1,sizeof(isroot)); memset(flag,0,sizeof(flag)); for(i=1;i<=n;i++) if(a.set[i]==i) { j=i; while(1) { if(flag[j]) break; flag[j]=1; j=pre[j]; } num=0; isroot[j]=num++; for(k=pre[j];k!=j;k=pre[k]) isroot[k]=num++; circle[i]=num; } memset(lca, -1, sizeof(lca)); memset(visit, 0, sizeof(visit)); b.init(n); for(i = 1; i <= n; i ++) if(isroot[i] != -1) DFS(i, 0, i); OutPut(); } }