40分,其他超时
查看原帖
40分,其他超时
1067789
Director_Ni楼主2024/11/20 20:46

感谢大佬

#include <bits/stdc++.h>
using namespace std;
///@param kb 真:在  假:无
const int N =4e5+2;
int s[N];
int k[N];
bool kb[N] ;
struct node
{
    // from就是下标
    vector<int> to;
} l[N];
void init(int n)
{
    for (int i = 0; i <= n ; ++i)
    {
        s[i] = i;kb[i]=1;
    }
}
int f(int a)
{
    return s[a] = a == s[a] ? s[a] : f(s[a]);
}
void ad(int a, int b)
{
    int ra = f(a), rb = f(b);
    s[ra] = rb;
}
int che(int n)
{
    int ret = 0;
    for (int i = 0; i <= n-1; ++i)
    {
        if(!kb[i])  continue;
        if (s[i] == i)
            ret++;
    }
    return ret;
}
int main()
{
    int n, m;
    cin >> n >> m;
    init(n);
    int u, v;
    int ans[200001], ansn = 0;
    for (int i = 1; i <= m; ++i)
    {
        cin >> u >> v;
        l[u].to.push_back(v);
        l[v].to.push_back(u);
    }
    ///@param kt 打击数
    int kt;
    cin >> kt;
    
    
    for (int i = 1; i <= kt; ++i)
    {
        cin >> k[i];
        kb[k[i]] = 0; // i寄了
    }
    ///@param cunzai 还在的
    vector<int> cunzai;
    for (int i = 1; i <= n; ++i)
    {
        if (kb[i])
        {
            cunzai.push_back(i);
        }
    }
    for (auto i : cunzai)
    {
        for (auto j : l[i].to)
        {
            if (kb[j])
            { // j在
                ad(i, j);
            }
        }
    }
   /* cout<<endl;
    for(int i=0;i<=n;++i){
    	cout<<s[i]<<" ";
	}*/
    ans[ansn++] = che(n);
    for (int i = kt; i >= 1; --i)
    { // 此时i未被打击
        int t=k[i];
        kb[t] = 1;
        cunzai.push_back(t);
        for (auto j : l[t].to)
        {
            if (kb[j])
            { // j在
                ad(t, j);
            }
        }
        ans[ansn++] = che(n);
    }
    for (int i = ansn-1 ; i >= 0; --i)
    {
        cout << ans[i] << endl;
    }
    
}
2024/11/20 20:46
加载中...