NC19778. 游戏
描述
输入描述
数据有多组，第一行一个整数T表示数据组数。
每组数据第一行有三个整数N, M, Q，表示玩家总数，好友关系数，以及日志记录的操作和小贝的查询次数。接下来M行，每一行有两个整数Ui, Vi, 表示玩家Ui, Vi是好友。接下来Q行每行描述一个日志或者查询操作，格式如下：
• i U, 玩家U进入了游戏
• o U, 玩家U离开了游戏
• q U, 询问玩家U所在的队伍有多少人
输出描述
对于每组数据第一行输出形如"Case #x:"，其中 x 为这组数据的编号（从1开始）。接下来若干行，每一行对应一个查询的答案。
示例1
输入:
1 3 2 7 1 2 2 3 i 1 i 3 q 1 i 2 q 1 o 2 q 1
输出:
Case #1: 1 3 2
C++14(g++5.4) 解法, 执行用时: 1462ms, 内存消耗: 124384K, 提交时间: 2018-10-02 15:53:31
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int pos;
int fa[610000],pp[110000];
int sz[610000],du[110000];
vector<int> g[110000];
int sx[110000];
const int N=500;
int f[1110][1110];
int now[110000];
int a[110000],na;
queue<int> que[110000];
int ys[110000];
char getop()
{
char x=getchar();
while (x!='i'&&x!='o'&&x!='q') x=getchar();
return x;
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void update(int x)
{
if (pp[x])
{
for (int i=1;i<=na;i++)
if (f[ys[x]][i]&&!sx[a[i]]) que[i].push(x);
while (!que[ys[x]].empty())
{
int y=que[ys[x]].front();
que[ys[x]].pop();
if (sx[y])
{
int fx=find(now[x]),fy=find(now[y]);
if (fx!=fy) fa[fx]=fy,sz[fy]+=sz[fx];
}
}
}
else
{
for (int i=0;i<g[x].size();i++)
if (pp[g[x][i]]&&!sx[g[x][i]]) que[ys[g[x][i]]].push(x);
for (int i=0;i<g[x].size();i++)
{
int y=g[x][i];
if (sx[y])
{
int fx=find(now[x]),fy=find(now[y]);
if (fx!=fy) fa[fx]=fy,sz[fy]+=sz[fx];
}
}
}
}
int main()
{
int T,cas=0;
scanf("%d",&T);
while (T--)
{
scanf("%d %d %d",&n,&m,&q);
for (int i=1;i<=n;i++)
fa[i]=0,sz[i]=du[i]=sx[i]=pp[i]=now[i]=0,g[i].clear();
pos=0;
for (int i=1;i<=m;i++)
{
int x,y;
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
du[x]++,du[y]++;
}
na=0;
for (int i=1;i<=n;i++)
if (du[i]>=N)
{
a[++na]=i;
pp[i]=1;
ys[i]=na;
while (!que[na].empty()) que[na].pop();
}
for (int i=1;i<=na;i++)
for (int j=1;j<=na;j++)
f[i][j]=0;
for (int i=1;i<=na;i++)
{
int x=a[i];
for (int j=0;j<g[x].size();j++)
if (pp[g[x][j]]) f[i][ys[g[x][j]]]=1;
}
printf("Case #%d:\n",++cas);
for (int i=1;i<=q;i++)
{
char op=getop();
int x;
scanf("%d",&x);
if (op=='i')
{
if (sx[x]) continue;
int tmp=now[x];
now[x]=++pos;
fa[pos]=pos;
sz[pos]=1;
if (tmp&&pp[x])
{
int fx=find(tmp);
sz[fx]++;
fa[pos]=fx;
}
sx[x]=1;
update(x);
}
else if (op=='o')
{
if (sx[x]==0) continue;
sx[x]=0;
int fx=find(now[x]);
sz[fx]--;
}
else
{
if (sx[x]==0)
{
printf("0\n");
continue;
}
int fx=find(now[x]);
printf("%d\n",sz[fx]);
}
}
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1501ms, 内存消耗: 84960K, 提交时间: 2020-03-08 23:34:11
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define dow(i,l,r) for(int i=r;i>=l;i--)
#define pb push_back
const int N=500500;
const int block=350;
int fa[N],num[N],vis[N],use[N],d[N],sz[N],n,m,q;
char s[10];
vector<int> g[N],gb[N],link[N];
int fx(int x)
{
return fa[x]==x?x:fa[x]=fx(fa[x]);
}
void merge(int x,int y)
{
x=fx(x),y=fx(y);
if(x==y) return;
if(sz[x]<sz[y]) swap(x,y);
sz[x]+=sz[y];
fa[y]=x;
}
void online(int x)
{
if(use[x])
{
for(auto too:gb[x])
if(!vis[too]) link[too].pb(x);
for(auto now:link[x])
if(vis[now]) merge(num[x],num[now]);
link[x].clear();
}
else
{
for(auto now:g[x])
if(use[now]&&!vis[now]) link[now].pb(x);
for(auto now:g[x])
if(vis[now]) merge(num[x],num[now]);
}
}
void solve()
{
scanf("%d %d %d",&n,&m,&q);
int tot=0;
rep(i,1,n) num[i]=d[i]=use[i]=vis[i]=0;
rep(i,1,n) link[i].clear(),g[i].clear(),gb[i].clear();
int j,k;
rep(i,1,m)
{
scanf("%d %d",&j,&k);
g[j].pb(k);
g[k].pb(j);
d[k]++,d[j]++;
}
rep(i,1,n)
if(d[i]>=block) use[i]=1;
rep(i,1,n)
if(use[i])
for(auto j:g[i])
if(use[j])
{
gb[i].pb(j);
gb[j].pb(i);
}
while(q--)
{
scanf("%s%d",s,&j);
if(s[0]=='i')
{
if(vis[j]) continue;
++tot;
fa[tot]=tot,sz[tot]=1;
if(num[j]&&use[j]) merge(tot,num[j]);
num[j]=tot;
vis[j]=1;
online(j);
}
else if(s[0]=='o')
{
if(!vis[j]) continue;
sz[fx(num[j])]--;
vis[j]=0;
}
else
printf("%d\n",vis[j]?sz[fx(num[j])]:0);
}
}
int main()
{
int tt;
scanf("%d",&tt);
rep(i,1,tt)
{
printf("Case #%d:\n",i);
solve();
}
return 0;
}