题解 洛谷P1197 星球大战

发布于 2019-06-10  25 次阅读


这题题目的意思是让我们拆点,而实际上我们并不需要按照题目所说的顺着做,而是可以倒着做,把拆点当做加点,这是这道题的核心思路

这里查询当前联通块的个数有一个技巧,就是在每加进去一个点时联通块个数加一,而如果这个点能与任意个联通块相连,且这个联通块的祖先不为当前节点的祖先(防止重复),则联通块的个数减一

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

#define int long long
#define N 2000100

using namespace std;

bool t[N];
int b[N],fa[N],prime[N];
int n,m,k,a1,b1,cnt=0,ans=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(x)]=anc(map[x][i]),--ans;
}
signed 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;
    ans=n-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--)
    {
        prime[i]=ans++;
        solve(b[i]);
        t[b[i]]=false;
    }
    prime[0]=ans;
    for (int i=0;i<=k;i++)
        cout<<prime[i]<<endl;
    return 0;
}

Cause this is the life. Living is do or die.