求助两种枚举边的方式造成的结果差异

P1197 [JSOI2008] 星球大战

Mr_think @ 2021-10-22 19:46:55

完整代码:

#include<cstdio>
using namespace std;
const int N=4e5+5;
int hd[N],to[N],nt[N],cnt;
inline void add(int x,int y){
    to[++cnt]=y,nt[cnt]=hd[x],hd[x]=cnt;
}
struct node{
    int x,y;
}b[N];
int fa[N],des[N];
bool vis[N];
int res,ans[N];
int find(int s){
    if(fa[s]==s) return s;
    return fa[s]=find(fa[s]);
}
void merge(int x,int y){fa[x]=y;}
int main(){
    int n,m; scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) fa[i]=i;
    for(int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        add(x,y),add(y,x);
        b[i].x=x,b[i].y=y;
    }
    int k;scanf("%d",&k);
    for(int i=1;i<=k;i++){
        scanf("%d",&des[i]);
        vis[des[i]]=1;
    }
    res=n-k;
//  for(int x=0;x<n;x++){
//      if(vis[x]) continue;
//      for(int i=hd[x];i;i=nt[i]){
//          int y=to[i];
//          if(vis[y]) continue;
//          x=find(x),y=find(y);
//          if(x!=y) merge(x,y),res++;
//      } 
//      
//  }
    for(int i=1;i<=m;i++){
        int x=b[i].x,y=b[i].y;
        if(vis[x]||vis[y]) continue;
        x=find(x),y=find(y);
        if(x!=y) merge(x,y),res--;
    }
    ans[k+1]=res;
    for(int j=k;j>=1;j--){
        int x=des[j];
        vis[x]=0;
        res++;
        for(int i=hd[x];i;i=nt[i]){
            int y=to[i];
            if(vis[y]) continue;
            x=find(x),y=find(y);
            if(x!=y) merge(x,y),res--;
        }
        ans[j]=res;
    }
    for(int i=1;i<=k+1;i++) printf("%d\n",ans[i]);
    return 0;
}
```cpp for(int x=0;x<n;x++){ if(vis[x]) continue; for(int i=hd[x];i;i=nt[i]){ int y=to[i]; if(vis[y]) continue; x=find(x),y=find(y); if(x!=y) merge(x,y),res++; } } ``` $AC$: ```cpp for(int i=1;i<=m;i++){ int x=b[i].x,y=b[i].y; if(vis[x]||vis[y]) continue; x=find(x),y=find(y); if(x!=y) merge(x,y),res--; } ```

by Mr_think @ 2021-10-22 19:48:27


by L_cm_C5H6 @ 2022-03-14 20:44:25

@Mr_think 第一种x被find修改了枚举少了,外围改一个枚举变量就过了


|