/*
给定n个数据中心，m份资料，每份资料在其中的两个中心备份，一天可供下载的时间是h小时
中心i在第hi小时需要维护，无法下载
现在要将一些中心的维护时间往后推1小时，使得任意时刻每份资料都可以被下载，请问最少选择多少个数据中心，
某个中心维护时，在其中资料无法下载，必须到其他点下载，
如果该点对应的点也在维护，那么这个对应点的维护必须往后推
对应点往后推时继续和其余点矛盾，那么其余点也要往后
所以，如果同一份数据的两个点相隔一小时，那么这两个点要么不推迟，要推迟就要一起推迟，
建立模型：点x和点y有相同的资料，并且hx+1==hy,那么加有向边(x,y)
最后得到的图中，一个强连通分量内的所有点必须一起选择
缩点构成DAG，选择出度为0的点即可
*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
struct Edge{
int to,nxt;}edge[maxn<<
2];
int n,m,t,h[maxn],head[maxn],tot,d[maxn][
2];
int c[maxn],low[maxn],dfn[maxn],stk[maxn],ins[maxn],ind,top;
int cnt;
vector<
int>
scc[maxn];
void tarjan(
int x){
dfn[x]=low[x]=++
ind;
stk[++top]=x;ins[x]=
1;
for(
int i=head[x];i!=-
1;i=
edge[i].nxt){
int y=
edge[i].to;
if(!dfn[y]){
//树枝边
tarjan(y);
low[x]=
min(low[x],low[y]);
}
else if(ins[y])
//后向边
low[x]=
min(low[x],dfn[y]);
}
if(dfn[x]==
low[x]){
cnt++
;
int y;
do{
y=stk[top--
];
ins[y]=
0;
c[y]=
cnt;scc[cnt].push_back(y);
}while(x!=
y);
}
}
void init(){
tot=
0;
memset(head,-
1,
sizeof head);
}
void addedge(
int u,
int v){
edge[tot].nxt=
head[u];
edge[tot].to=
v;
head[u]=tot++
;
}
int in[maxn],
out[maxn];
int main(){
init();
cin>>n>>m>>
t;
for(
int i=
1;i<=n;i++)scanf(
"%d",&
h[i]);
for(
int i=
1;i<=m;i++)scanf(
"%d%d",&d[i][
0],&d[i][
1]);
for(
int i=
1;i<=m;i++){
//建图
if((h[d[i][
0]]+
1)%t==h[d[i][
1]])
addedge(d[i][0],d[i][
1]);
if((h[d[i][
1]]+
1)%t==h[d[i][
0]])
addedge(d[i][1],d[i][
0]);
}
for(
int i=
1;i<=n;i++
)
if(!
dfn[i])
tarjan(i);
for(
int x=
1;x<=n;x++
)
for(
int i=head[x];i!=-
1;i=
edge[i].nxt){
int y=
edge[i].to;
if(c[x]==c[y])
continue;
in[c[y]]++;
out[c[x]]++
;
}
int ans=
0x3f3f3f3f,k;
for(
int i=
1;i<=cnt;i++
)
if(
out[i]==
0 && scc[i].size()<
ans)
k=i,ans=
scc[i].size();
cout<<ans<<
endl;
for(
int i=
0;i<scc[k].size();i++
)
printf("%d ",scc[k][i]);
}
转载于:https://www.cnblogs.com/zsben991126/p/10464493.html
相关资源：各显卡算力对照表！
