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=;

 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]=;

     for(int i=head[u];i;i=e[i].nxt){

         int v=e[i].to;

         if(dfn[v]==){

             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]=;

         }while(x!=u);

     }

 }

 int main(){

     scanf("%d%d%d",&n,&m,&h);

     for(int i=;i<=n;i++){

         scanf("%d",&t[i]);

     }

     for(int i=;i<=m;i++){

         scanf("%d%d",&a[i],&b[i]);

         if(t[a[i]]+==t[b[i]]||(t[a[i]]==h-&&t[b[i]]==))add(a[i],b[i]);

         if(t[b[i]]+==t[a[i]]||(t[b[i]]==h-&&t[a[i]]==))add(b[i],a[i]);

     }

     for(int i=;i<=n;i++){

         if(dfn[i]==)Tarjan(i);

     }

     for(int i=;i<=m;i++){

         if(c[a[i]]==c[b[i]])continue;

         if(t[a[i]]+==t[b[i]]||(t[a[i]]==h-&&t[b[i]]==))deg[c[a[i]]]++;

         if(t[b[i]]+==t[a[i]]||(t[b[i]]==h-&&t[a[i]]==))deg[c[b[i]]]++;

     }

     int minn=;

     for(int i=n+;i<=n+num;i++){

         if(deg[i]==&&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 ;

 }