首页 > 代码库 > bzoj1015题解

bzoj1015题解

2024-09-05 16:46:17   218人阅读

【题意分析】

　　给你一张无向图，要求支持删点和询问连通块数。

【解题思路】

　　可以直接可持久化并查集大力艹过去。

　　考虑到正着删点就是倒着加点，所以并不需要可持久化。复杂度O((k+m)α(n))。

【参考代码】

　　当时还在玩泥巴，实现有点naive，常数奇大无比。。

技术分享
 1 #include<cstdio> 2 #include<cstring> 3 #include<set> 4 #define REP(I,start,end) for(int I=start;I<=end;I++) 5 #define PER(I,start,end) for(int I=start;I>=end;I--) 6 using namespace std; 7 set<int> tree; 8 int n,m,k,edge=0,q[400001],father[400001],head[400001],next[400001],point[400001],sav[400001]; 9 bool destroyed[400001];10 inline void addEdge(int from,int to)11 {12     next[++edge]=head[from];13     head[from]=edge;14     point[edge]=to;15 }16 inline int getFa(int n)17 {18     if(father[n]==n)19         return n;20     return father[n]=getFa(father[n]);21 }22 int main()23 {24     scanf("%d%d",&n,&m);25     REP(i,1,m)26     {27         int u,v;28         scanf("%d%d",&u,&v);29         addEdge(u,v);30         addEdge(v,u);31     }32     scanf("%d",&k);33     memset(destroyed,0,sizeof(destroyed));34     REP(i,1,k)35     {36         scanf("%d",q+i);37         destroyed[q[i]]=true;38     }39     REP(i,0,n-1)40         father[i]=i;41     REP(i,0,n-1)42         if(!destroyed[i])43         {44             int t=head[i];45             while(t)46             {47                 int p=point[t];48                 if(!destroyed[p])49                     father[getFa(p)]=getFa(i);50                 t=next[t];51             }52         }53     tree.clear();54     REP(i,0,n-1)55     {56         int fa=getFa(i);57         if(!destroyed[i]&&tree.find(fa)==tree.end())58             tree.insert(fa);59     }60     sav[k]=tree.size();61     PER(i,k-1,0)62     {63         int P=q[i+1],t=head[P];64         destroyed[P]=false;65         tree.clear();66         while(t)67         {68             int p=point[t];69             if(!destroyed[p])70             {71                 int fa2=getFa(p);72                 tree.insert(fa2);73                 father[getFa(P)]=fa2;74             }75             t=next[t];76         }77         sav[i]=sav[i+1]-tree.size()+1;78     }79     REP(i,0,k)80         printf("%d\n",sav[i]);81     return 0;82 }
View Code

 

bzoj1015题解


联系
我们