自动搬运

查看原文

来自洛谷，原作者为

	Graphcity 循此苦旅，终抵繁星。

搬运于2025-08-24 22:19:07，当前版本为作者最后更新于2020-05-23 16:50:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于这道题，我们可以建图解决问题。

在这题所构造的图中，如果点 $a$ 连向了点 $b$ , 则表示现在正在观看频道 $a$ 时会有一个人把频道调到 $b$ 。

样例 3 建的图差不多是这样子的：

我们可以试着再把图化简一下：

每次要调整频道时，只会让最年轻的人来调整，所以对于每个点，只要保留它第一次连的边就行了。

可以发现，当走到入度为 0 的结点时，就没有人会调频道了，可以输出答案。而且，当两次都经过同一个点时，就表示老人们会一直循环调整频道，输出 -1 结束程序即可。

代码如下：

#include<bits/stdc++.h>
#define Maxn int(1e5)
using namespace std;

int n,m,now,ans;//now:目前所在的结点 
int nxt[Maxn+5];//nxt[x]表示x连接的那一条边 
int vis[Maxn+5];//vis[x]记录x结点经过了几次 

int main()
{
	scanf("%d%d%d",&n,&m,&now);
	for(register int i=1;i<=n;++i)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		if(!nxt[b]) nxt[b]=a;//连边 
	}
	while(nxt[now])
	{
		if(++vis[now]>1)//特判无解 
		{
			printf("-1");
			return 0;
		}
		now=nxt[now];
		++ans;
	}
	printf("%d",ans);
    return 0;
}