codeforces 949C - Data Center Maintenance【tarjan】

首先转换图论模型，把某个客户一个终端的维修时间(+1)%h之后和另一个终端维修时间一样，这样的两个终端连一条有向边，表示推后一个终端就必须推后另一个

然后tarjan缩点，一个scc里的终端是要一起推迟的，scc内点数为新图点权

根据贪心的思想，在缩完点的DAG里，一定是出度为0的点能获得更小的值，因为出度不为零的点还要加上出边所能到的点的点权

直接在出度为0的点里取min，然后记一下更新答案的新点，最后把属于这个新点的点的编号输出即可

#include<iostream>

#include<cstdio>

using namespace std;

const int N=1000005;

int n,m,q,a[N],h[N],cnt,low[N],dfn[N],tot,bl[N],col,s[N],top,d[N],va[N],mn=1e9,w;

bool v[N];

struct qwe

{

	int ne,no,to;

}e[N];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].no=u;

	e[cnt].to=v;

	h[u]=cnt;

}

void tarjan(int u)

{

	dfn[u]=low[u]=++tot;

	v[s[++top]=u]=1;

	for(int i=h[u];i;i=e[i].ne)

	{

		if(!dfn[e[i].to])

		{

			tarjan(e[i].to);

			low[u]=min(low[u],low[e[i].to]);

		}

		else if(v[e[i].to])

			low[u]=min(low[u],dfn[e[i].to]);

	}

	if(low[u]==dfn[u])

	{

		col++;

		while(s[top]!=u)

		{

			bl[s[top]]=col;

			va[col]++;

			v[s[top--]]=0;

		}

		bl[s[top]]=col;

		va[col]++;

		v[s[top--]]=0;

	}

}

int main()

{

	n=read(),m=read(),q=read();

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

		a[i]=read();

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

	{

		int x=read(),y=read();

		if((a[x]+1)%q==a[y])

			add(x,y);

		if((a[y]+1)%q==a[x])

			add(y,x);

	}

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

		if(!dfn[i])

			tarjan(i);

	for(int i=1;i<=cnt;i++)

		if(bl[e[i].no]!=bl[e[i].to])

			d[bl[e[i].no]]++;

	for(int i=1;i<=col;i++)

		if(!d[i]&&va[i]<mn)

			mn=va[i],w=i;

	printf("%d\n",mn);

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

		if(bl[i]==w)

			printf("%d ",i);

	return 0;

}