题解 P6264 【[COCI2014/2015#3]DOM】

· · 题解

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

在这题所构造的图中，如果点 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;
}