chichow @ 2020-02-10 16:00:01
这数组都开这么多了怎么还RE
#include <cstdio>
#include <queue>
#include <queue>
#include <stack>
#define M 200110
using namespace std;
int n,m,fa[401010];
bool in_st[401010];
vector<int>e[201010];
stack<int>st;
stack<int>ans;
int getFa(int x){
if (x==fa[x]) return x;
return fa[x] = getFa(fa[x]);
}
int main(){
int i,j,k,x,y;
scanf("%d%d",&n,&m);
for (i=0; i<m; i++){
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
for (i=0; i<n; i++) in_st[i]=false,fa[i]=i;
scanf("%d",&k);
for (i=0; i<k; i++){
scanf("%d",&x);
in_st[x] = true;
st.push(x);
}
int cnt=n-k;
for (i=0; i<n; i++){
if (in_st[i]) continue;
x = i;
for (j=0; j<e[x].size(); j++){
y = e[x][j];
if (in_st[y]) continue;
if (getFa(x)!=getFa(y)){
fa[fa[x]] = fa[y];
cnt--;
}
}
}
while(!st.empty()){
ans.push(cnt);
cnt++;
x = st.top();st.pop();
in_st[x] = false;
for (j=0; j<e[x].size(); j++){
y = e[x][j];
if (in_st[y]) continue;
if (getFa(x)!=getFa(y)){
fa[fa[x]] = fa[y];
cnt--;
}
}
}
ans.push(cnt);
while(!ans.empty()){
printf("%d\n",ans.top());
ans.pop();
}
return 0;
}
by chichow @ 2020-02-10 16:05:58
真的邪呼,干脆把M开到300010,还RE 那就400010吧! 无语了
by Chinese_cabbage @ 2020-03-31 09:45:39
你再多开一点每个数组后面加个0,应该就行了
by __int114514 @ 2020-03-31 21:03:56
@Chinese_cabbage 好久不见