CF949C Data Center Maintenance（建图+强联通分量）

题意

有 n 个信息中心，第 i 个信息中心要在第 ti 个小时维护，维护期间信息不能被获得。

每个用户的数据都有两份备份，第 i 个用户的数据放在信息中心 c(i,1) 和 c(i,2)。

现在要挑选一个尽量小的信息中心集合，使得将这个集合的维护时间推迟一个小时后，仍然能保证每个用户的数据在任意时刻都能获得。

n≤100000

题解

对于每对 c(i,1),c(i,2)，若调整 c(i,1) 后与 c(i,2) 的维护时间冲突，则连边 (c(i,1), c(i,2) )

对于 c(i,2),c(i,1) 亦然

求出强连通分量，所求集合即为缩点后度数为 0 的最小的 SCC

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=500100;
int cnt,head[N];
int dfn[N],low[N],stack[N],vis[N],w[N],c[N],num,tot,top;
int n,m,h,t[N],ans,a[N],b[N],deg[N];
struct edge{
    int to,nxt;
}e[N];
void add(int u,int v){
    cnt++;
    e[cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
void Tarjan(int u){
    dfn[u]=low[u]=++tot;
    stack[++top]=u;
    vis[u]=1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(dfn[v]==0){
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v])low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        int x;
        num++;
        do{
            x=stack[top--];
            c[x]=num+n;
            w[num+n]++;
            add(num+n,x);
            vis[x]=0;
        }while(x!=u);
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&h);
    for(int i=1;i<=n;i++){
        scanf("%d",&t[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a[i],&b[i]);
        if(t[a[i]]+1==t[b[i]]||(t[a[i]]==h-1&&t[b[i]]==0))add(a[i],b[i]);
        if(t[b[i]]+1==t[a[i]]||(t[b[i]]==h-1&&t[a[i]]==0))add(b[i],a[i]);
    }
    for(int i=1;i<=n;i++){
        if(dfn[i]==0)Tarjan(i);
    }
    for(int i=1;i<=m;i++){
        if(c[a[i]]==c[b[i]])continue;
        if(t[a[i]]+1==t[b[i]]||(t[a[i]]==h-1&&t[b[i]]==0))deg[c[a[i]]]++;
        if(t[b[i]]+1==t[a[i]]||(t[b[i]]==h-1&&t[a[i]]==0))deg[c[b[i]]]++;
    }
    int minn=9999999;
    for(int i=n+1;i<=n+num;i++){
        if(deg[i]==0&&minn>w[i]){
            minn=w[i];
            ans=i;
        }
    }
    printf("%d\n",w[ans]);
    for(int i=head[ans];i;i=e[i].nxt){
        int v=e[i].to;
        printf("%d ",v);
    } 
    return 0;
}