luogu P1197 [JSOI2008]星球大戰 并查集 逆向思維 鄰接表

題目

剛開始做的時候每一次摧毀都初始化一次 毫無懸念的tle 複雜度O(k*(n+m))

後來瞄了一眼題解 把正向的摧毀改成反向的建立 結果還是tle 複雜度O(k*m)

再仔細看題解才發現不能用

father[i]==i
           

來判讀聯通塊的數量

應該要用鄰接表把所有的邊都存起來 然後再建立星球的時候先加答案 然後再掃一遍所有的邊 看能不能把兩個不同聯通塊連在一起

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#define test cout<<"*"<<endl;
using namespace std;
const int N=1000000;
vector<int>g[N];
int father[N],dis[N],a[N],n,m;
void init()
{
    for(int i=0;i<=n;i++)
    {
        father[i]=i;
    }
}
int Find(int x)
{
    if(x==father[x])return x;
    father[x]=Find(father[x]);
    return father[x];
}
bool unite(int x,int y)
{
    int tx=Find(x);
    int ty=Find(y);
    if(tx==ty)return 0;
    father[ty]=tx;
    return 1;
}
int b[N],ans[N];
int tj()//聯通塊的數目
{
    int sum=0;
    for(int i=0;i<n;i++)
    {
        if(!b[i]&&father[i]==i)
        {
            sum++;
        }
    }
    return sum;
}
int main()
{
    int k,x,y;
    scanf("%d%d",&n,&m);
    init();
    for(int i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    scanf("%d",&k);
    for(int i=0;i<k;i++)
    {
        scanf("%d",&a[i]);
        b[a[i]]=1;
    }
    for(int i=0;i<n;i++)
        if(!b[i])
            for(int j=0;j<g[i].size();j++)
                if(!b[g[i][j]])
                    unite(i,g[i][j]);
    ans[k]=tj();
    for(int i=k-1;i>=0;i--)
    {
        b[a[i]]=0;
        ans[i]=ans[i+1]+1;//多了一個點 先加一
        for(int j=0;j<g[a[i]].size();j++)
        {
            if(b[g[a[i]][j]])continue;
            if(unite(g[a[i]][j],a[i]))
                ans[i]--;
        }
//        cout<<"i="<<i<<" ans[i]="<<ans[i]<<endl;
    }
    for(int i=0;i<=k;i++)
        printf("%d\n",ans[i]);
    return 0;
}