10分求助

P1197 [JSOI2008] 星球大战

日月童羽 @ 2019-08-24 10:26:03

10分求助!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;

int n, m, p, oo, ll[400005], tot, ans[400005], fa[400005];
bool bj[400005];
int a[400005], b[400005][3];

int find(int x)
{
    if(fa[x] == x) return x;
    else return fa[x] = find(fa[x]);
}

void lianjie(int from, int next)
{
    b[oo][0] = from;
    b[oo][2] = a[from];
    b[oo][1] = next;
    a[from] = oo;
    oo++;
}

int main ()
{
//  freopen("out","r",stdin);
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        fa[i] = i;
        a[i] = -1;
    }
    for(int i = 0; i < m; i++)
    {
        int k, l;
    //  oo = i;
        cin >> k >> l;
        lianjie(k, l);
        lianjie(l, k);
    }
    cin >> p;
    tot = n - p;
    for(int i = 1; i <= p; i++)
    {
        int pp;
        cin >> pp;
        bj[pp] = 1;
        ll[i] = pp; 
    }
    for(int i = 0; i < 2 * m; i++)
    {
        if(!bj[b[i][0]] && !bj[b[i][1]])
        {
            if(find(b[i][0]) != find(b[i][1]))
            {
                tot--;
                fa[find(b[i][0])] = fa[find(b[i][1])];
            }
        }
    }
    ans[p + 1] = tot;
    for(int i = p; i >= 1; i--)
    {
        bj[i] = 0;
        int xx = ll[i];
        tot++;
        int yy = a[xx];
        while(yy != -1)
        {
        //  cout << "shdfkjhs" << "   ";
            if(find(b[yy][0]) != find(b[yy][1]) && !bj[b[yy][1]])
            {
                tot--;
                fa[find(b[yy][1])] = fa[find(b[yy][0])];
            }   
            yy = b[yy][2];
        }
        ans[i] = tot;
    }
    for(int i = 1; i <= p + 1; i++)
    {
        cout << ans[i] << endl;
    }
}

|