BZOJ 1015 并查集+离线倒序

统计块个数写错了调了好久啊,BZOJ1696的弱化版本。

 #include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
#define fi first
#define se second
#define mp make_pair
#define pa pair<int,int>
using namespace std;
inline void Get_Int(int &x)
{
x=; char ch=getchar(); int f=;
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();} x*=f;
}
inline void Put_Int(int x)
{
char ch[]; int top=;
if (x==) ch[++top]='';
while (x) ch[++top]=x%+'',x/=;
while (top) putchar(ch[top--]); putchar('\n');
} const int Maxn=;
int father[Maxn],head[Maxn],Ans[Maxn],res,u[Maxn],cnt,v[Maxn],n,m,Q,Pos[Maxn];
bool b[Maxn],ret[Maxn];
struct Edge{int to,next;}edge[Maxn<<];
int getfather(int x) {if (x==father[x]) return x; return father[x]=getfather(father[x]);}
inline void Merge(int u,int v) {father[getfather(u)]=getfather(v);}
inline void Add(int u,int v) {edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt++;}
inline void Build()
{
for (int i=;i<=n;i++)
{
if (b[i]) continue;
for (int j=head[i];j!=-;j=edge[j].next) if (!b[edge[j].to]) Merge(i,edge[j].to);
}
} int main()
{
Get_Int(n),Get_Int(m);
for (int i=;i<=n;i++) father[i]=i;
memset(head,-,sizeof(head)); cnt=;
memset(b,false,sizeof(b));
for (int i=;i<=m;i++) Get_Int(u[i]),Get_Int(v[i]),Add(u[i]+,v[i]+),Add(v[i]+,u[i]+);
Get_Int(Q);
for (int i=;i<=Q;i++) Get_Int(Pos[i]),Pos[i]++,b[Pos[i]]=true;
Build();
memset(ret,false,sizeof(ret));
for (int i=;i<=n;i++) ret[getfather(i)]=true;
int res=; for (int i=;i<=n;i++) if (ret[i]) res++;//写成了ret[getfather[i]]了>_<
res-=Q;
for (int i=Q;i>=;i--)
{
Ans[i]=res;
b[Pos[i]]=false;
for (int j=head[Pos[i]];j!=-;j=edge[j].next)
if (!b[edge[j].to])
if (getfather(Pos[i])!=getfather(edge[j].to)) res--,Merge(Pos[i],edge[j].to);
res++;
}
Ans[]=res;
for (int i=;i<=Q;i++) Put_Int(Ans[i]);
return ; }

C++

上一篇:Oracle expdp/impdp 使用示例


下一篇:C#--图片上传(PC端和APP)保存及 跨域上传说明