\(Description:\)
给出 \(n\) 台机子，每台机子有一个信息，每个信息由两台机子维护，现在要在 \(h\) 小时内对一些机子进行维护，维护时长一小时，现在要求所有时刻都可以取出任何信息，求做少要推迟那些中心，如果时间等于 \(h\) 变为 \(0\)
\(Sample\) \(Input:\)
3 3 5
4 4 0
1 3
3 2
3 1
\(Sample\) $Output: $
1
3
\(Solution:\)
考虑其实如果两个机子的维修时间 满足
\(t[c_1]+1 \equiv t[c_2] \pmod {h}\)
说明这个时候我们如果推迟 \(c_1\)
那么也得推迟 \(c_2\)
反一反同理，但是这有什么用呢？
考虑我们对于要求同时推迟的两台连一条有向边，这样可以构成一张图。
那么这张图上如果选一个点，那么所有他连出去的点都要延迟，那么很明显，只要出度最小就是最优的。
但是发现这个图可能会有强联通分量，那么就缩个点，发现这个强联通分量里的点都是必须同时推迟。
那么再选出度最小的前提下，我们那也得要求这个块的点个数最小。
#include<bits/stdc++.h>
using namespace std;
int n,m,h,ans,cnt,num,Min,En,sum;
const int N=1e5+5;
int head[N],deg[N],t[N],scc[N],c[N][2];
int size[N],ins[N],dfn[N],low[N];
vector <int> tt[N];
stack <int> s;
struct edge {
int next,to;
}E[N<<1];
inline void add(int from,int to){
E[++En].next=head[from];
E[En].to=to;
head[from]=En;
}
inline void tarjan(int u){
ins[u]=1; s.push(u);
dfn[u]=low[u]=++num;
for(int i=head[u];i;i=E[i].next){
int v=E[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v])
low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
scc[u]=++cnt;
ins[u]=0;
tt[cnt].push_back(u);
while(s.top()!=u){
int v=s.top();
ins[v]=0;
scc[v]=cnt;
tt[cnt].push_back(v);
s.pop();
}
s.pop();
}
}
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",&c[i][0],&c[i][1]);
if((t[c[i][0]]+1)%h==t[c[i][1]]%h) add(c[i][0],c[i][1]);
if((t[c[i][1]]+1)%h==t[c[i][0]]%h) add(c[i][1],c[i][0]);
}
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
for(int i=1;i<=m;++i){
if(scc[c[i][0]]==scc[c[i][1]]) continue;
if((t[c[i][0]]+1)%h==t[c[i][1]]%h) deg[scc[c[i][0]]]++;
if((t[c[i][1]]+1)%h==t[c[i][0]]%h) deg[scc[c[i][1]]]++;
}
Min=ans=0x3f3f3f3f;
for(int i=1;i<=cnt;++i) Min=min(deg[i],Min);
for(int i=1;i<=cnt;++i)
if(Min==deg[i] && (int)tt[i].size()<ans)
ans=tt[i].size(),sum=i;
printf("%d\n",ans);
for(int i=0;i<(int)tt[sum].size();++i)
printf("%d ",tt[sum][i]);
putchar('\n');
return 0;
}