tarjan
题意: 有n个数据维护中心,每个在h小时中需要1个小时维护,有m个雇主,他们的中心分别为c1,c2,要求这两个数据中心不能同时维护。
现在要挑出一个数据中心的子集,把他们的维护时间都推后一个小时。问最小推几个?
建图,如果对于一个顾客,两个数据维护中心维护时间正好差一个小时,那么前者向后者连一条边。在一个强连通分量里面的所有点必须选。。如果有连向其他的强连通分量,那么那个也必须选,这种情况肯定不是最优,所以舍弃所有有出度的强连通分量。
tarjan缩点,然后判一判。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
using namespace std;
const int inf = 0x3f3f3f3f;
const LL LLinf = 0x3f3f3f3f3f3f3f3f;
LL read()
{
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10ll+ch-'0';ch=getchar();}
return x*f;
} const int maxn = 100000 + 10;
const int maxm = 200000 + 10; struct Edge {
int to,nex;
}e[maxm]; int n,m,h;
int u[maxn];
int g[maxn],eid; void addedge(int a,int b) {
e[eid]=(Edge){b,g[a]}; g[a]=eid++;
} void build()
{
n=read(); m=read(); h=read();
for(int i=1;i<=n;i++)
{
u[i]=read();
} memset(g,-1,sizeof(g));
for(int i=1,c1,c2;i<=m;i++)
{
c1=read(); c2=read();
if((u[c1]+1)%h==u[c2])
{
addedge(c1,c2);
//printf(" %d %d\n",c1,c2);
}
if((u[c2]+1)%h==u[c1])
{
addedge(c2,c1);
//printf(" %d %d\n",c2,c1);
}
}
} int dfn[maxn],low[maxn],cnt;
bool instack[maxn];
int s[maxn],sp;
int color[maxn],cp;
int sum[maxn];
int out[maxn];
int res; void tarjan(int u)
{
dfn[u]=low[u]=++cnt;
s[++sp]=u; instack[u]=1; for(int i=g[u];~i;i=e[i].nex)
{
if(!dfn[e[i].to])
{
tarjan(e[i].to);
low[u]=min(low[u],low[e[i].to]);
}
else if(instack[e[i].to])
{
low[u]=min(low[u],dfn[e[i].to]);
}
} if(dfn[u]==low[u]) {
++cp; int v;
while(sp)
{
v=s[sp];
instack[v]=0;
color[v]=cp;
sum[cp]++;
sp--;
if(s[sp+1]==u) break;
}
}
} void solve()
{
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
/*
for(int i=1;i<=n;i++)
printf("color[%d]=%d\n",i,color[i]);
*/
/*for(int i=1;i<=n;i++)
if(!color[i])
{
color[i]=++cp;
sum[i]=1;
}
*/
for(int u=1;u<=n;u++) { for(int i=g[u];~i;i=e[i].nex) if(color[e[i].to]!=color[u])
out[color[u]]++;
} res=0; sum[0]=inf;
for(int i=1;i<=cp;i++) {
//printf("Test %d %d\n",i,out[i]);
if(out[i]==0&&sum[i]<sum[res])
{
res=i;
}
}
printf("%d\n",sum[res]);
for(int i=1;i<=n;i++) if(color[i]==res)
printf("%d ",i);
printf("\n");
} int main()
{
build();
solve(); return 0;
}