bzoj1015: [JSOI2008]星球大战starwar 并查集+离线处理
2021-07-10 04:04
阅读:476
标签:namespace find add div etc hid ext http jsoi2008
题目传送门
这道题可以改为离线处理 倒着找答案 这样删点就变成加点了 有了这个思想题目就很好写了哇 23333


#include#include #include using namespace std; const int M=400007; int read(){ int ans=0,f=1,c=getchar(); while(c‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();} while(c>=‘0‘&&c‘9‘){ans=ans*10+(c-‘0‘); c=getchar();} return ans*f; } int n,m,k,tot,sum; int fa[M],ans[M],usd[M],in[M],first[M],q[M]; struct node{int to,next;}e[2*M]; void ins(int a,int b){sum++; e[sum].to=b; e[sum].next=first[a]; first[a]=sum;} void insert(int a,int b){ins(a,b); ins(b,a);} int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);} void add(int x){ int p=find(x); for(int i=first[x];i;i=e[i].next){ int now=e[i].to; if(usd[now]){ int q=find(now); if(p!=q){fa[q]=p; tot--;} } } } int main() { int x,y; n=read(); m=read(); for(int i=0;i i; for(int i=1;iread(),insert(x,y); k=read(); for(int i=1;iin[q[i]]=1; for(int i=0;i if(!in[i]){ tot++; add(i); usd[i]=1; } ans[k+1]=tot; for(int i=k;i;i--){ tot++; add(q[i]); usd[q[i]]=1; ans[i]=tot; } for(int i=1;i1;i++) printf("%d\n",ans[i]); return 0; }
bzoj1015: [JSOI2008]星球大战starwar 并查集+离线处理
标签:namespace find add div etc hid ext http jsoi2008
原文地址:http://www.cnblogs.com/lyzuikeai/p/7091189.html
下一篇:websocket小荔枝
文章来自:搜素材网的编程语言模块,转载请注明文章出处。
文章标题:bzoj1015: [JSOI2008]星球大战starwar 并查集+离线处理
文章链接:http://soscw.com/index.php/essay/103057.html
文章标题:bzoj1015: [JSOI2008]星球大战starwar 并查集+离线处理
文章链接:http://soscw.com/index.php/essay/103057.html
评论
亲,登录后才可以留言!