RE+WA求调,悬赏一关
查看原帖
RE+WA求调,悬赏一关
635780
BeBanned楼主2023/6/18 08:43

vector存图,样例没过

#include <iostream>
#include <vector>
using namespace std;
vector<int> adj[400005];
int n, m;
int k; 
int des[400005];
int cntlian;
int fa[400005];
int ans[400005];
bool broken[400005];
struct edge
{
    int u, v;
}e[400005];
int cnt = 0;
int find(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= m;i ++)
    {
        int u, v;
        cin >> u >> v;
        e[++ cnt] = edge{u, v};
        e[++ cnt] = edge{v, u};
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin >> k;
    cntlian = n - k; 
    for(int i = 1;i <= k;i ++)
    {
        cin >> des[i];
        broken[des[i]] = true;
    }
    for(int i = 0;i < n;i ++) fa[i] = i;
    for(int i = 1;i <= 2 * m;i ++)
    {
        if(!broken[e[i].u] && !broken[e[i].v])
        {
            int fu = find(e[i].u);
            int fv = find(e[i].v);
            if(fu != fv)
            {
                fa[fv] = fu;
                cntlian --;
            }
        }
    }
    ans[k + 1] = cntlian;
    for(int i = k;i >= 1;i --)//貌似这部分有问题
    {
        int u = des[i];
        cntlian ++;
        broken[u] = false;
        for(int j = 0;j < adj[u].size();j ++)
        {
            int v = adj[u][i];
            if(broken[v]) continue;
            int fu = find(u);
            int fv = find(v);
            if(fu != fv)
            {
                fa[fv] = fu;
                cntlian --;
            }
        }
        ans[i] = cntlian;
    }
    for(int i = 1;i <= k + 1;i ++)
    {
        cout << ans[i] << endl;
    }
    return 0;
}
2023/6/18 08:43
加载中...