题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1015

题意：给出一个图。每次删掉一个点，求删掉之后连通块个数。

思路：正着做不好做，我们反正想，那么题目就变成每次添加一个点（其实就是添加若干条边）之后连通块个数。这就可以使用并查集了。。

vector<int> g[N];
int n,m,Q,a[N],s[N],sz[N],h[N],ans[N];

int find(int x)
{
    if(s[x]!=x) s[x]=find(s[x]);
    return s[x];
}

int sum;

void Union(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        sum--;
        if(sz[x]<sz[y])
        {
            sz[y]+=sz[x];
            s[x]=y;
        }
        else
        {
            sz[x]+=sz[y];
            s[y]=x;
        }
    }
}

int main()
{
    RD(n,m);
    int i,j,k,u,v;
    FOR1(i,m)
    {
        RD(u,v);
        g[u].pb(v),g[v].pb(u);
    }
    FOR0(i,n) s[i]=i,sz[i]=1;
    RD(Q);
    FOR1(i,Q) RD(a[i]),h[a[i]]=1;
    sum=n;
    FOR0(i,n) if(!h[i]) FOR0(j,SZ(g[i])) if(!h[g[i][j]])
    {
        Union(i,g[i][j]);
    }
    int x=Q;
    FORL1(i,Q)
    {
        ans[i]=sum-x;
        x--;
        h[a[i]]=0;
        FOR0(j,SZ(g[a[i]])) if(!h[g[a[i]][j]])
        {
            Union(a[i],g[a[i]][j]);
        }
    }
    PR(sum);
    FOR1(i,Q) PR(ans[i]);
    return 0;
}

最新文章

1. Nginx ssl证书部署
2. 【el表达式】jsp中设置默认图像
3. activemq安全设置 设置admin的用户名和密码
4. apache AllowEncodedSlashes 允许URL中对路径分隔符进行编码
5. 【py网页】urllib.urlretrieve远程下载
6. 小白日记51：kali渗透测试之Web渗透-WebShell（中国菜刀、WeBaCoo、Weevely）
7. javascript 引擎Rhino源代码分析 浅析 实例函数对象及this
8. 百度编辑器ueditor简单易用
9. 基于visual Studio2013解决面试题之1309求子集
10. 这么多的技术，作为一个freshman，什么研究？
11. iOS XIB等比例适配
12. TensorFlow tutorial
13. Boosting Static Representation Robustness for Binary Clone Search against Code Obfuscation and Compiler Optimization(二)
14. Java线程基础（二）
15. Git 基础和原理
16. Injection
17. GetCheckProxy
18. LINUX部署SVN服务器
19. Vivado HLS初识---阅读《vivado design suite tutorial-high-level synthesis》（2）
20. DDOS hulk,rudy

热门文章

1. 如何优化C语言代码(程序员必读)
2. HTML5中表单验证的8种方法(转)
3. jQuery1.9.1--attr,prop与val方法源码分析
4. c#实现串口操作 SerialPort
5. make_pair() (STL)
6. java 格式化代码 不进行换行
7. Session、Cookie及cache的区别
8. python_ftplib实现通过FTP下载文件
9. 教你使用UIWindow实现窗口的切换
10. 《从零开始学习jQuery》及《jQuery风暴》学习笔记