萌新求助,简单大水题

P1197 [JSOI2008] 星球大战

樱初音斗橡皮 @ 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

呜呜呜


|