并查集
这是一道很棒的并查集类问题，具有较高的思维难度。注意到题目中所描述的猴子的连接方式，有可能猴子a抓住猴子b的尾巴，也有可能b抓住a的尾巴，也有可能a和b互相抓住对方的尾巴。其实我们只关心两个猴子是否相连，以上三种情况都是猴子a和b相连。现在题目要求的就是每只猴子第一次直接或间接脱离猴子1的时间。看起来好像和并查集的操作是相反的，那我们就反过来求解。首先求出时刻m所有放手行为都执行后猴子们的连接情况，然后从时刻m往前反过来执行“抓尾巴”行为，这样问题转化为求每个猴子第一次直接或间接与猴子1相连的时刻。这正是并查集所支持的操作，只是每次将猴子1所在集合与其它集合合并时，需要把那个集合的所有猴子的答案都设置为这个时刻。我们可以另外对每个集合维护一个链表，包含这个集合的所有猴子，合并时将链表合并。这样总的时间复杂度不变，问题成功解决。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | #include <iostream> using namespace std; struct node { int v; node *next; node(int v,node *next):v(v),next(next) {} } *first[200002],*last[200002]; int d[400004][2],holdOrig[200002][2],holdCur[200002][2],ans[200002],f[200002]; int getRoot(int v) { if(f[v]==v) return v; else return f[v]=getRoot(f[v]); } void unite(int a,int b) { int x=getRoot(a),y=getRoot(b); if(x!=y) { f[x]=y; last[y]->next=first[x]; last[y]=last[x]; } } void uniteAndUpdateAns(int a,int b,int moment) { int x=getRoot(a),y=getRoot(b); if(x!=y) { if(x==getRoot(1)) for(node *t=first[y];t;t=t->next) ans[t->v]=moment; else if(y==getRoot(1)) for(node *t=first[x];t;t=t->next) ans[t->v]=moment; f[x]=y; last[y]->next=first[x]; last[y]=last[x]; } } int main() { int n,m; memset(ans,-1,sizeof(ans)); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { scanf("%d%d",&holdOrig[i][0],&holdOrig[i][1]); holdCur[i][0]=holdOrig[i][0]; holdCur[i][1]=holdOrig[i][1]; } for(int i=0;i<m;++i) { scanf("%d%d",&d[i][0],&d[i][1]); --d[i][1]; holdCur[d[i][0]][d[i][1]]=-1; } for(int i=1;i<=n;++i) { f[i]=i; first[i]=last[i]=new node(i,NULL); } for(int i=1;i<=n;++i) { if(holdCur[i][0]>-1) unite(i,holdCur[i][0]); if(holdCur[i][1]>-1) unite(i,holdCur[i][1]); } for(int i=m-1;i>-1;--i) if(holdOrig[d[i][0]][d[i][1]]>-1) uniteAndUpdateAns(d[i][0],holdOrig[d[i][0]][d[i][1]],i); for(int i=1;i<=n;++i) printf("%d\n",ans[i]); return 0; } |