若是城市A和城市B互通，城市B和城市C互通，那麼城市A和城市C也互通，A、B、C三個城市算一個匯集點。先已知有n個城市和m條道路，想求的是有幾個匯集點？但小S以爲太簡單了，因爲戰爭緣由，某些城市會被導彈銷燬掉，與之相應的道路也變得不可用。以前已經被銷燬的不會被複原。現給定每次銷燬的城市順序，求每次銷燬後匯集點有多少個。node
第一行輸入n和m，表示城市數量和道路數量(1≤n≤104，1≤m≤2n)(1≤n≤104，1≤m≤2n)ios
接下來m行，每行輸入兩個數ai和bi(1≤ai,bi≤n)(1≤ai,bi≤n)。表示ai和bi直接有道路c++
第m+2行輸入q，表示有q個城市會被銷燬 (1≤q≤n)(1≤q≤n)spa
接下來輸入q個數，每行輸入一個不重複的數，表示被銷燬的城市code
輸出一行q個數，每i個數表示第i個城市銷燬後匯集點的數量ci
8 9 1 2 1 3 1 6 2 4 3 6 4 5 4 7 5 7 5 8 4 3 2 5 4
1 2 3 3
並查集，經過儲存節點反向建樹，以後再一個個加點尋找集合個數it
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
struct node{
int a,b;
bool flag;//已經加過的點無須再加，經過flag進行標記
}node[maxn<<1];
int pre[maxn<<1];
int n,m,t;
vector<int> res;//儲存須要刪除的節點
stack<int> st;//儲存集合個數
bool vis[maxn<<1];
int find(int x)
{
return pre[x]=(pre[x]==x?x:find(pre[x]));//狀態壓縮
}
void unite(int x,int y)
{
x=find(x),y=find(y);
if(x>y) pre[x]=y;//秩低向秩高的合併，防止樹的退化
else pre[y]=x;
}
int main()
{
ios::sync_with_stdio(false);
memset(vis,0,sizeof(vis));
cin>>n>>m;
for(int i=1;i<=n;i++)
pre[i]=i;
for(int i=0;i<m;i++)
{
cin>>node[i].a>>node[i].b;
node[i].flag=false;
}
cin>>t;
for(int i=0;i<t;i++)
{
int tmp;
cin>>tmp;
vis[tmp]=true;//標記已經被刪除的點
res.push_back(tmp);
}
vector<int>::iterator it;
/*it=res.end()-1;
for(int i=0;i<m;i++)
{
if(!vis[node[i].a]&&!vis[node[i].b]&&!node[i].flag)
{
unite(node[i].a,node[i].b);
node[i].flag=true;
cout<<i<<endl;
}
}*/
while(t--)
{
it=res.end()-1;
for(int i=0;i<m;i++)
{
if(!vis[node[i].a]&&!vis[node[i].b]&&!node[i].flag)
{
unite(node[i].a,node[i].b);
node[i].flag=true;
}
}
int sum=0;
for(int i=1;i<=n;i++)
if(find(i)==i) sum++;
st.push(sum);
vis[*it]=false;//加點
res.erase(it);
}
int cnt=1;
while(!st.empty())
{
cout<<st.top()-cnt++<<' ';
st.pop();
}
cout<<endl;
return 0;
}
應有更快的解法io