题意:有n(3<=n<=100000)个点组成的无向图,保证任意两点间只有一个neighbour点,有两种操作,LENGTH x y求x y之间的最短距离,
若不存在输出-1,DELETE x表示删除第x条边。对于每个LENGTH 询问输出答案。
题解:想想会发现图的一个性质,所有三角形挂在同一个点上,这样首先处理下找出中心后,维护非中心点的同在一个三角形内的另一个点的编号,
像中心方向的边和非中心方向的边是否删除即可。
Sure原创,转载请注明出处
#include <iostream> #include <cstdio> #include <memory.h> using namespace std; const int maxn = 100002; struct node { int v; bool center,other; }po[maxn]; int indegree[maxn],U[maxn * 3],V[maxn * 3]; char str[10]; int m,n,c; void swap(int &a,int &b) { int tmp = a; a = b; b = tmp; return; } void init() { memset(indegree,0,sizeof(indegree)); scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) { po[i].v = -1; po[i].center = po[i].other = true; } return; } void read() { for(int i=0;i<m;i++) { scanf("%d %d",&U[i],&V[i]); indegree[U[i]]++; indegree[V[i]]++; } int d = 0; for(int i=1;i<=n;i++) { if(indegree[i] > d) { d = indegree[i]; c = i; } } return; } void make() { for(int i=0;i<m;i++) { if(U[i] != c && V[i] != c) { po[U[i]].v = V[i]; po[V[i]].v = U[i]; } else if(V[i] == c) swap(U[i] , V[i]); } return; } void solve() { int x,y; while(~scanf("%s",str)) { if(str[0] == 'L') { scanf("%d %d",&x,&y); if(x == y) puts("0"); else if(x == c || y == c) { if(y == c) swap(x , y); if(po[y].center) puts("1"); else if(po[y].other && po[po[y].v].center) puts("2"); else puts("-1"); } else if(po[x].v == y) { if(po[x].other) puts("1"); else if(po[x].center && po[y].center) puts("2"); else puts("-1"); } else { int a = -1,b = -1; if(po[x].center) a = 1; else if(po[x].other && po[po[x].v].center) a = 2; if(po[y].center) b = 1; else if(po[y].other && po[po[y].v].center) b = 2; if(a == -1 || b == -1) puts("-1"); else printf("%d\n",a+b); } } else { scanf("%d",&x); x--; if(U[x] != c && V[x] != c) { po[U[x]].other = po[V[x]].other = false; } else { po[V[x]].center = false; } } } return; } int main() { init(); read(); make(); solve(); return 0; }