[关闭]
@ysner 2018-07-25T16:06:11.000000Z 字数 1862 阅读 1829

星球联盟

并查集


题面

个点,条边的不联通图。一一加入条边,每加入一条就询问该边所在边双联通分量的点数。

解析

该题解法与公园逛一题算法有异曲同工之妙。
怎样生成边双?在生成树上加一条边,边的两端点树上路径中的所有点互为边双。

于是先要构出一棵生成树。
先用并查集维护点之间的联通性,把条边中的树边(边两端点不联通)连了,标记非树边。
然而图可能还是不联通,而只有几个大联通块。把它们与结点相连即可。
生成树构建完毕。预处理一下点的父亲和深度,方便以后跑树上路径。

接下来开始针对非树边。(并查集要清空)
根据生成边双方法,我们应该把边的两端点树上路径中的所有点并入同一个并查集。
从深度大的端点开始,不断往上跳,将结点与结点父亲合并,同时统计并查集大小之和即可。

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #define re register
  8. #define il inline
  9. #define ll long long
  10. #define max(a,b) ((a)>(b)?(a):(b))
  11. #define min(a,b) ((a)<(b)?(a):(b))
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=5e5+100;
  16. struct Edge{int to,nxt;}e[N<<1];
  17. struct dat{int u,v,vis;}a[N<<1];
  18. int n,m,p,f[N],ff[N],d[N],sz[N],cnt,h[N];
  19. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  20. il ll gi()
  21. {
  22. re ll x=0,t=1;
  23. re char ch=getchar();
  24. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  25. if(ch=='-') t=-1,ch=getchar();
  26. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  27. return x*t;
  28. }
  29. il int find(re int x){return x==f[x]?x:f[x]=find(f[x]);}
  30. il void Merge(re int u,re int v)
  31. {
  32. while(u^v)
  33. {
  34. if(d[u]<d[v]) swap(u,v);
  35. re int fu=find(u),fv=find(ff[fu]);
  36. if(fu^fv) f[fu]=fv,sz[fv]+=sz[fu];
  37. u=fv;
  38. }
  39. }
  40. il void dfs(re int u,re int fa)
  41. {
  42. ff[u]=fa;d[u]=d[fa]+1;
  43. for(re int i=h[u];i+1;i=e[i].nxt)
  44. {
  45. re int v=e[i].to;
  46. if(v==fa) continue;
  47. dfs(v,u);
  48. }
  49. }
  50. int main()
  51. {
  52. memset(h,-1,sizeof(h));
  53. n=gi();m=gi();p=gi();
  54. fp(i,1,n) f[i]=i;
  55. fp(i,1,m+p)
  56. {
  57. re int u=gi(),v=gi(),fu=find(u),fv=find(v);
  58. if(fu^fv) add(u,v),add(v,u),f[fu]=fv,a[i].vis=0;
  59. else a[i].vis=1;
  60. a[i].u=u;a[i].v=v;
  61. }
  62. fp(i,1,n)
  63. {
  64. re int fu=find(1),fv=find(i);
  65. if(fu^fv) add(1,i),add(i,1),f[fv]=fu;
  66. }
  67. dfs(1,0);
  68. fp(i,1,n) f[i]=i,sz[i]=1;
  69. fp(i,1,m)
  70. if(a[i].vis)
  71. {
  72. re int u=a[i].u,v=a[i].v,fu=find(u),fv=find(v);
  73. if(fu^fv) Merge(fu,fv);
  74. }
  75. fp(i,m+1,m+p)
  76. if(a[i].vis)
  77. {
  78. re int u=a[i].u,v=a[i].v,fu=find(u),fv=find(v);
  79. if(fu^fv) Merge(fu,fv);
  80. printf("%d\n",sz[find(fu)]);
  81. }
  82. else puts("No");
  83. return 0;
  84. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注