我为什么那么菜啊

P1197 [JSOI2008] 星球大战

ex_jason @ 2019-05-29 14:45:05

只有10分

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>

#define N 200100

using namespace std;

bool t[N];
int b[N],fa[N],prime[N];
int n,m,k,a1,b1,cnt=0;
vector <int> map[N];
int anc(int x)
{
    if (fa[x]==x) return x;
    fa[x]=anc(fa[x]);
    return fa[x];
}
void addedge(int x,int y)
{
    map[x].push_back(y);
}
void solve(int x)
{
    for (int i=0;i<map[x].size();i++)
        if (!t[map[x][i]])
            {
                if (anc(map[x][i])<anc(x)) fa[anc(map[x][i])]=anc(x);
                else fa[anc(x)]=anc(map[x][i]);
            }
}
void find()
{
    int ans=0;
    for (int i=0;i<n;i++)
        if (fa[i]==i && (!t[b[i]]) ) ans++;
    cnt++;
    prime[cnt]=ans;
    return;
}
int main()
{
    cin>>n>>m;
    for (int i=0;i<n;i++)
        fa[i]=i;
    for (int i=1;i<=m;i++)
    {
        cin>>a1>>b1;
        addedge(a1,b1);
        addedge(b1,a1);
    }
    cin>>k;
    for (int i=1;i<=k;i++)
    {
        cin>>b[i];
        t[b[i]]=true;
    }
    for (int i=0;i<n;i++)
        if (!t[i]) solve(i);
    for (int i=k;i>=1;i--)
    {
        find();
        solve(b[i]);
        t[b[i]]=false;
    }
    find();
    for (int i=cnt;i>=1;i--)
        cout<<prime[i]<<endl;
    return 0;
}

by d3NtMDAw @ 2019-06-01 16:51:13

你不用中考的嘛


by d3NtMDAw @ 2019-06-01 20:10:51

@ex_jason 话说你最后是怎么改的啊?。。。


|