森林---其实就是计算森林中父节点的个数

题目：http://oj.jxust.edu.cn/contest/Problem?id=1561&pid=2

大意：求森林中根节点的个数，然后删除某个点，更新根节点的个数。

#include "iostream"
#include "vector"
using namespace std;
const int N =1e4+10;
int result[N],fa[N],city[N];//记录结果,根节点,销毁点
bool vis[N];//标记；
std::vector<int> v[N];//用邻接法存储树
int n,m,q;
int find(int x)
{
    return fa[x]=(fa[x]==x?x:find(fa[x]));//匹配父节点
}
int main(int argc, char const *argv[]) {
        std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//输入输出加速模板
        cin>>n>>m;
        for(int i=0;i<n;i++) fa[i]=i;
        for(int i=0;i<m;i++)
        {
                int a,b;
                cin>>a>>b;
                v[a].push_back(b);
                v[b].push_back(a);
        }
        cin>>q;
        for(int i=0;i<q;i++)
        {
                cin>>city[i];
                vis[city[i]]=1;
        }

        //更新父子节点
        for(int i=0;i<n;i++)
        {
                if(!vis[i])
                {
                        for(auto x:v[i])
                        if(!vis[x]){//未被摧毁
                                fa[find(x)]=find(i);//i的子节点的父节点==i的父节点
                        }
                }
        }
        int ans=0;
        for(int i=0;i<n;i++) if(!vis[i]&&find(i)==i) ans++;
        result[q-1]=ans;//聚集点的个数m个根节点
        for(int i=q-1;i>=0;i--)
        {
                ans++;//                                       修复一个然后++；嘿嘿！
                vis[city[i]]=false;//先修复一个
                for(auto x:v[city[i]])
                {
                        if(!vis[x]&&find(x)!=find(city[i]))//x未被摧毁 && x的根节点不等于city的根节点
                        {
                                ans--;//修复后编入city[i]的子节点集
                                fa[find(x)]=find(city[i]);//更新树
                        }
                }
                result[i-1]=ans;

        }
        for(int i=0;i<q;i++)
        {
                cout<<result[i];
                if(i!=q-1) cout<<" ";
                if(i==q-1) cout<<endl;
        }
        return 0;
}