C题解 | 小欧皇 | TOp

#include <stdio.h>
#include <stdbool.h>

int *to, *nxt, *head;  // global adjacency arrays
int idx;

static inline int find(int x, int p[]) { // DSU find with path compression
    while (x != p[x]) x = p[x] = p[p[x]];
    return x;
}

void add(int u,int v){                   // add edge
    to[++idx]=v;
    nxt[idx]=head[u];
    head[u]=idx;
}

int main(void){
    int n,m; 
    scanf("%d%d",&n,&m);
    char s[n+1]; 
    scanf("%s",s+1);

    // allocate arrays on stack (VLA)
    int p[n+1], sz[n+1], head_arr[n+2], to_arr[2*m+2], nxt_arr[2*m+2];
    bool occ[n+1], seen[n+1];

    // bind global pointers to local arrays
    to = to_arr; nxt = nxt_arr; head = head_arr;

    // initialize
    for(int i=1;i<=n;i++){occ[i]=s[i]=='1';p[i]=i;sz[i]=1;head[i]=0;seen[i]=0;}

    // build adjacency & union occupied cities
    for(int i=0,u,v;i<m;i++){
        scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
        if(occ[u]&&occ[v]){
            int a=find(u,p), b=find(v,p);
            if(a!=b){
                if(sz[a]<sz[b]){int t=a;a=b;b=t;}
                p[b]=a; sz[a]+=sz[b];
            }
        }
    }

    long base=0;
    for(int i=1;i<=n;i++)               // initial profit
        if(occ[i]&&find(i,p)==i)
            base+=1LL*sz[i]*(sz[i]-1)/2;

    long best=base; int city=1;

    // evaluate each unoccupied city
    for(int u=1;u<=n;u++) if(!occ[u]){
        long loss=0,sum=1;
        for(int e=head[u];e;e=nxt[e]){  // scan neighbors
            int v=to[e]; if(!occ[v]) continue;
            int r=find(v,p);
            if(!seen[r]){               // avoid duplicate comps
                seen[r]=1;
                loss+=1LL*sz[r]*(sz[r]-1)/2;
                sum+=sz[r];
            }
        }
        long newp=base-loss+1LL*sum*(sum-1)/2;
        if(newp>best||(newp==best&&u<city)) best=newp,city=u;
        for(int e=head[u];e;e=nxt[e]){int v=to[e];if(occ[v])seen[find(v,p)]=0;} // reset flags
    }

    printf("%d %lld\n",city,best);
    return 0;
}