题意
有 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
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const int N=500100; 8 int cnt,head[N]; 9 int dfn[N],low[N],stack[N],vis[N],w[N],c[N],num,tot,top; 10 int n,m,h,t[N],ans,a[N],b[N],deg[N]; 11 struct edge{ 12 int to,nxt; 13 }e[N]; 14 void add(int u,int v){ 15 cnt++; 16 e[cnt].nxt=head[u]; 17 e[cnt].to=v; 18 head[u]=cnt; 19 } 20 void Tarjan(int u){ 21 dfn[u]=low[u]=++tot; 22 stack[++top]=u; 23 vis[u]=1; 24 for(int i=head[u];i;i=e[i].nxt){ 25 int v=e[i].to; 26 if(dfn[v]==0){ 27 Tarjan(v); 28 low[u]=min(low[u],low[v]); 29 } 30 else if(vis[v])low[u]=min(low[u],dfn[v]); 31 } 32 if(low[u]==dfn[u]){ 33 int x; 34 num++; 35 do{ 36 x=stack[top--]; 37 c[x]=num+n; 38 w[num+n]++; 39 add(num+n,x); 40 vis[x]=0; 41 }while(x!=u); 42 } 43 } 44 int main(){ 45 scanf("%d%d%d",&n,&m,&h); 46 for(int i=1;i<=n;i++){ 47 scanf("%d",&t[i]); 48 } 49 for(int i=1;i<=m;i++){ 50 scanf("%d%d",&a[i],&b[i]); 51 if(t[a[i]]+1==t[b[i]]||(t[a[i]]==h-1&&t[b[i]]==0))add(a[i],b[i]); 52 if(t[b[i]]+1==t[a[i]]||(t[b[i]]==h-1&&t[a[i]]==0))add(b[i],a[i]); 53 } 54 for(int i=1;i<=n;i++){ 55 if(dfn[i]==0)Tarjan(i); 56 } 57 for(int i=1;i<=m;i++){ 58 if(c[a[i]]==c[b[i]])continue; 59 if(t[a[i]]+1==t[b[i]]||(t[a[i]]==h-1&&t[b[i]]==0))deg[c[a[i]]]++; 60 if(t[b[i]]+1==t[a[i]]||(t[b[i]]==h-1&&t[a[i]]==0))deg[c[b[i]]]++; 61 } 62 int minn=9999999; 63 for(int i=n+1;i<=n+num;i++){ 64 if(deg[i]==0&&minn>w[i]){ 65 minn=w[i]; 66 ans=i; 67 } 68 } 69 printf("%d\n",w[ans]); 70 for(int i=head[ans];i;i=e[i].nxt){ 71 int v=e[i].to; 72 printf("%d ",v); 73 } 74 return 0; 75 }