题解#非原创!!!

#转载#

为了解决这个问题，我们需要进行如下步骤：

读取输入数据：读取村庄数量 ( n )，道路数量 ( m )，和参数 ( k )，以及每条道路的连接关系。
构建图结构：使用邻接表来表示有向图，记录每个村庄可以直接到达的其他村庄。
检测环路：利用深度优先搜索（DFS）来检测图中是否存在环路。如果存在环路，则输出 "No 不清醒"；否则输出 "Yes 清醒"。
计算输出值：如果不存在环路，则根据给定的 ( k ) 值计算相应的结果。

def is_cycle_present(n, adj):
    visited = [False] * (n + 1)
    rec_stack = [False] * (n + 1)
    
    def dfs(v):
        if not visited[v]:
            visited[v] = True
            rec_stack[v] = True
            
            for neighbor in adj[v]:
                if not visited[neighbor] and dfs(neighbor):
                    return True
                elif rec_stack[neighbor]:
                    return True
            
        rec_stack[v] = False
        return False
    
    for i in range(1, n + 1):
        if not visited[i]:
            if dfs(i):
                return True
    
    return False

def solve(n, m, k, edges):
    # Build adjacency list
    adj = [[] for _ in range(n + 1)]
    for x, y in edges:
        adj[x].append(y)
    
    # Check for cycle
    if is_cycle_present(n, adj):
        print("No")
        print(k**2)
    else:
        print("Yes")
        print(pow(2, k, 9997))

import sys
input = sys.stdin.read().splitlines()
n, m, k = map(int, input[0].split())
edges = []
for i in range(1, m + 1):
    x, y = map(int, input[i].split())
    edges.append((x, y))

solve(n, m, k, edges)

is_cycle_present 函数：利用深度优先搜索（DFS）来检测图中是否存在环路。如果在DFS的过程中某个节点被访问过但还在递归栈中，则说明存在环路。
solve 函数：主函数负责读取输入，构建图的邻接表，调用检测环路函数，并根据结果输出相应的清醒状态和计算值。
输出：根据是否存在环路来输出 "Yes/No 清醒/不清醒" 和对应的计算值。
这样的实现保证了对输入数据的有效处理，并根据图的特性来判断老爷爷在乡间行走时是否会因为兜圈子而昏沉。