求调

illuple @ 2023-11-04 20:38:25

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define repi(a,n) for(int i=(a);i<(n);++i) 
#define repj(a,n) for(int j=(a);j<(n);++j)
#define lb(a,n,i) lower_bound(a,a+n,i)
#define ub(a,n,i) upper_bound(a,a+n,i)
#define pri priority_queue
template<class t>
void read(t& a)
{
    int f=1;a=0;
    char c=getchar();
    while(!isdigit(c))
    {
        f=(c=='-')?-1:f;
        c=getchar();
    }
    while(isdigit(c))
    {
        a=a*10+c-'0';
        c=getchar();
    }
    a*=f;
    return;
}
int BUF[100];
template<class t>
void write(t a)
{
    BUF[1]=0;
    int p=0;
    if(a<0)
    {
        putchar('-');
        a=-a;
    }
    if(a==0) p++;
    while(a)
    {
        BUF[++p]=a%10;
        a/=10;
    }
    for(int i=p;i>=1;i--)
    {
        putchar(BUF[i]+'0');
    }
    return;
}
struct edge{
    int from,cost,to,cap;
    bool operator<(const edge& e)const
    {
        return cost>e.cost;
    }
    edge(int from=0,int cost=0,int to=0,int cap=0):
        from(from),cost(cost),to(to),cap(cap){} };
pri<edge>que;
const ll maxn=1e6;
int n,m;
int f[maxn],r[maxn];
vector<int>g[maxn];
int d[maxn];
int sans;
bool bro[maxn];
vector<int>ans;
void inti()
{
    for(int i=0;i<=maxn;++i) f[i]=i;
    memset(r,0,sizeof(r));
    memset(bro,0,sizeof(bro));
}
int find(int x) {return x==f[x]?x:f[x]=find(f[x]);}
void unite(int x,int y)
{
    x=find(x);y=find(y);
    if(x==y) return;
    sans--;
    if(r[x]>r[y]) f[y]=x;
    else f[x]=y,r[y]=(r[x]==r[y]?r[y]+1:r[y]);
    return;
}
int main()
{
    inti();
    cin>>n>>m;sans=n;
    repi(0,m){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);};
    int k;cin>>k;
    repi(0,k){cin>>d[i];bro[d[i]]=1;};
    repi(0,n) {if(!bro[i]) for(auto it:g[i]) {if(!bro[it]) unite(it,i);}};ans.push_back(sans);
    for(int i=k-1;i>=0;i--){bro[d[i]]=0;for(auto it:g[d[i]]){if(!bro[it])unite(it,d[i]);};ans.push_back(sans);};
    a.
    for(auto i:ans)cout<<i<<"\n";
    return 0;
}

by illuple @ 2023-11-04 20:49:15

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define repi(a,n) for(int i=(a);i<(n);++i) 
#define repj(a,n) for(int j=(a);j<(n);++j)
#define lb(a,n,i) lower_bound(a,a+n,i)
#define ub(a,n,i) upper_bound(a,a+n,i)
#define pri priority_queue
template<class t>
void read(t& a)
{
    int f=1;a=0;
    char c=getchar();
    while(!isdigit(c))
    {
        f=(c=='-')?-1:f;
        c=getchar();
    }
    while(isdigit(c))
    {
        a=a*10+c-'0';
        c=getchar();
    }
    a*=f;
    return;
}
int BUF[100];
template<class t>
void write(t a)
{
    BUF[1]=0;
    int p=0;
    if(a<0)
    {
        putchar('-');
        a=-a;
    }
    if(a==0) p++;
    while(a)
    {
        BUF[++p]=a%10;
        a/=10;
    }
    for(int i=p;i>=1;i--)
    {
        putchar(BUF[i]+'0');
    }
    return;
}
struct edge{
    int from,cost,to,cap;
    bool operator<(const edge& e)const
    {
        return cost>e.cost;
    }
    edge(int from=0,int cost=0,int to=0,int cap=0):
        from(from),cost(cost),to(to),cap(cap){} };
pri<edge>que;
const ll maxn=1e6;
int n,m;
int f[maxn],r[maxn];
vector<int>g[maxn];
int d[maxn];
int sans;
bool bro[maxn];
vector<int>ans;
void inti()
{
    for(int i=0;i<=maxn;++i) f[i]=i;
    memset(r,0,sizeof(r));
    memset(bro,0,sizeof(bro));
}
int find(int x) {return x==f[x]?x:f[x]=find(f[x]);}
void unite(int x,int y)
{
    x=find(x);y=find(y);
    if(x==y) return;
    sans--;
    if(r[x]>r[y]) f[y]=x;
    else f[x]=y,r[y]=(r[x]==r[y]?r[y]+1:r[y]);
    return;
}
int main()
{
    inti();
    cin>>n>>m;sans=n;
    repi(0,m){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);};
    int k;cin>>k;
    repi(0,k){cin>>d[i];bro[d[i]]=1;};
    repi(0,n) {if(!bro[i]) for(auto it:g[i]) {if(!bro[it]) unite(it,i);}};ans.push_back(sans);
    for(int i=k-1;i>=0;i--){bro[d[i]]=0;for(auto it:g[d[i]]){if(!bro[it])unite(it,d[i]);};ans.push_back(sans);};
    for(int i=ans.size()-1;i>=0;--i) cout<<ans[i]<<"\n";
    return 0;
}

by illuple @ 2023-11-04 21:01:29

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define repi(a,n) for(int i=(a);i<(n);++i) 
#define repj(a,n) for(int j=(a);j<(n);++j)
#define lb(a,n,i) lower_bound(a,a+n,i)
#define ub(a,n,i) upper_bound(a,a+n,i)
#define pri priority_queue
template<class t>
void read(t& a)
{
    int f=1;a=0;
    char c=getchar();
    while(!isdigit(c))
    {
        f=(c=='-')?-1:f;
        c=getchar();
    }
    while(isdigit(c))
    {
        a=a*10+c-'0';
        c=getchar();
    }
    a*=f;
    return;
}
int BUF[100];
template<class t>
void write(t a)
{
    BUF[1]=0;
    int p=0;
    if(a<0)
    {
        putchar('-');
        a=-a;
    }
    if(a==0) p++;
    while(a)
    {
        BUF[++p]=a%10;
        a/=10;
    }
    for(int i=p;i>=1;i--)
    {
        putchar(BUF[i]+'0');
    }
    return;
}
struct edge{
    int from,cost,to,cap;
    bool operator<(const edge& e)const
    {
        return cost>e.cost;
    }
    edge(int from=0,int cost=0,int to=0,int cap=0):
        from(from),cost(cost),to(to),cap(cap){} };
pri<edge>que;
const ll maxn=1e6;
int n,m;
int f[maxn],r[maxn];
vector<int>g[maxn];
int d[maxn];
int sans;
bool bro[maxn];
vector<int>ans;
void inti()
{
    for(int i=0;i<=maxn;++i) f[i]=i;
    memset(r,0,sizeof(r));
    memset(bro,0,sizeof(bro));
}
int find(int x) {return x==f[x]?x:f[x]=find(f[x]);}
void unite(int x,int y)
{
    x=find(x);y=find(y);
    if(x==y) return;
    sans--;
    if(r[x]>r[y]) f[y]=x;
    else f[x]=y,r[y]=(r[x]==r[y]?r[y]+1:r[y]);
    return;
}
bool same(int x,int y){return find(x)==find(y);};
int main()
{
    inti();
    cin>>n>>m;sans=n;
    repi(0,m){int x,y;cin>>x>>y;g[x].push_back(y);g[y].push_back(x);};
    int k;cin>>k;
    repi(0,k){cin>>d[i];bro[d[i]]=1;};
    repi(0,n) {if(!bro[i]) for(auto it:g[i]) {if(!bro[it]&&!same(i,it)) unite(it,i);}};ans.push_back(sans);
    for(int i=k-1;i>=0;i--){bro[d[i]]=0;sans++;for(auto it:g[d[i]]){if(!bro[it]&&!same(d[i],it))unite(it,d[i]);};ans.push_back(sans);};
    for(auto it:ans) cout<<it<<"\n";
    return 0;
}