樱初音斗橡皮 @ 2019-03-01 20:28:39
RT,第九个点蜜汁WA
#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
using std::scanf;
using std::printf;
int n, m;
int fa[200002];
int findanc(int x)
{
if (x==fa[x])
return x;
else
return fa[x]=findanc(fa[x]);
}
void merge(int x, int y)
{
x=findanc(x), y=findanc(y);
fa[x]=y;
}
const int N=400002;
int head[N];
struct node
{
int to, nxt, wei;
} edge[N];
int cnt=0;
void add_edge(int f, int t, int w=1)
{
cnt++;
edge[cnt].to=t;
edge[cnt].nxt=head[f];
edge[cnt].wei=w;
head[f]=cnt;
return;
}
int d[N];
bool del[N];
bool vis[N];
inline void del_edge(const int& f)
{
del[f]=true;
return;
}
void bfs(int i)
{
std::queue<int> q;
for (int j=head[i]; j!=-1; j=edge[j].nxt)
{
int t=edge[j].to;
if (!del[t]&&!vis[t])
q.push(t), vis[t]=true, merge(t, i);
}
while (!q.empty())
{
int t=q.front();
q.pop();
for (int j=head[t]; j!=-1; j=edge[j].nxt)
{
int tt=edge[j].to;
if (!del[tt]&&!vis[tt])
q.push(tt), vis[tt]=true, merge(tt, i);
}
}
return;
}
std::stack<int> aaa;
int main()
{
scanf("%d%d", &n, &m);
for (int i=1; i<=n; i++)
fa[i]=i;
for (int i=1; i<=n; ++i)
head[i]=-1;
for (int i=1; i<=m; ++i)
{
int f, t;
scanf("%d%d", &f, &t);
add_edge(f+1, t+1);
add_edge(t+1, f+1);
}
int k;
scanf("%d", &k);
for (int i=1; i<=k; ++i)
{
scanf("%d", d+i);
d[i]++;
del_edge(d[i]);
}
int ans=0;
for (int i=1; i<=n; ++i)
if (!del[i]&&!vis[i])
vis[i]=true, bfs(i), ++ans;
ans+=k;
aaa.push(ans-k);
for (int i=k; i>=1; --i)
{
del[d[i]]=false;
for (int j=head[d[i]]; j!=-1; j=edge[j].nxt)
{
int t=edge[j].to;
if (!del[t]&&findanc(d[i])!=findanc(t))
--ans, merge(d[i], t);
}
aaa.push(ans-i+1);
}
while (!aaa.empty())
{
int t=aaa.top();
aaa.pop();
printf("%d\n", t);
}
return 0;
}
by _Felix @ 2019-03-01 20:32:43
巨佬眼中蓝题十分简单
呜呜呜
by aminoas @ 2019-03-01 20:33:41
呜呜呜