求助大佬,MLE+TLE 只有20分

P1197 [JSOI2008] 星球大战

萧瑟 @ 2019-12-31 18:11:37

#include<bits/stdc++.h>
using namespace std;
int k,cnt,fa[200010],n,m,s,a[200010],b[200010],top;
bool v[200010];
struct edge {
    int he,to;
}e[200010];
 inline int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
 }
int main(){
    cin>>n>>m;
    for(int i=0;i<m;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        e[i].he=x;
        e[i].to=y;
    }
    cin>>k;
    for(int i=0;i<n;++i){
        fa[i]=i;
    }
    for(int i=k;i>0;--i){
        int u;
        scanf("%d",&u);
        a[i]=u;
        fa[u]=-1;
        v[u]=1; 
    }
    for(int i=1;i<=k+1;++i){ 
    int ans=0,x1=i-1;
    if(x1!=0)
    fa[a[x1]]=a[x1];
    v[a[x1]]=0;
    for(int i=0;i<m;++i){
        int x,y;
        x=e[i].he;
        y=e[i].to;
        if(v[x]==0&&v[y]==0){
        int f1,f2;
        f1=find(x);
        f2=find(y);
        fa[f1]=f2;  
    }
    } 
    for(int i=0;i<n;++i){
        if(fa[i]==i)ans++;
    }
    b[top++]=ans;
    } 
    for(int i=top-1;i>=0;--i){
        printf("%d\n",b[i]);
    }
    return 0;
}

by CreeperLordVader @ 2019-12-31 18:32:32

@萧瑟 错解


by 萧瑟 @ 2019-12-31 20:15:30

@CreeperLordVader 大佬为什么?能给蒟蒻分析一下吗?


|