weixin_53488249 2022-04-13 16:43 采纳率: 100%
浏览 32
已结题

python有向图的环问题

描述
如果有这么三个人a,b,c,并且a爱上b,b爱上c,c爱上a这样一个循环,那么我们就把这种包含三个人的循环定义为“奇怪的循环”。我们给出一群人的爱慕关系,目标是找出这些爱慕关系中有多少这种狗血的“奇怪的循环”。

输入
输入共包括n+1行,第一行为正整数n,下面紧跟n行;
每行包括两个名字A,B并用空格隔开,表示A爱上了B
(输入数据保证一个人只爱另外一个人,不存在一个人爱多个人的情况)

输出
输出一个整数,共包含多少个“奇怪的循环”。

样例输入
4
Alice Bob
Bob Carol
Carol Alice
Syf None

样例输出
1

提示
样例中Alice,Bob,Carol就是这么一个循环

  • 写回答

1条回答 默认 最新

  • 陈年椰子 2022-04-14 17:20
    关注

    这个题目,有点意思
    有没有更多的测试样例?

    val_n = int(input())
    val_dict = {}
    for i in range(val_n):
        val_input = input().split(" ")
        if len(val_input)==2:
            val_dict[val_input[0]] = val_input[1]
    
    # print(val_dict)
    val_dict_len = len(val_dict)
    val_circle_lst = []
    for k,v in val_dict.items():
        p1 = k
        p2 = v
        val_p_list = [p1,p2]
        for i in range(val_dict_len-1):
            if p2 in val_dict:
                p2 = val_dict[p2]
            else:
                break
            if p2 == p1:
                # 判断是否有重复的图
                temp1 = val_p_list.copy()
                temp1.sort()
                if temp1 not in val_circle_lst:
                    # 不重复,记录
                    # print(val_p_list)
                    val_circle_lst.append(temp1)
                break
            else:
                val_p_list.append(p2)
    
    print(len(val_circle_lst))
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 5月8日
  • 已采纳回答 4月30日
  • 创建了问题 4月13日

悬赏问题

  • ¥15 UltraScale 系列 Bitslip 技术支持
  • ¥15 一个线程在sleep的时候set一个信号会起作用吗
  • ¥100 需求高精度PT100设计电路和算法
  • ¥15 单片机配网,继电器开关,广播
  • ¥60 Qcustomplot绘制实时动态曲线
  • ¥20 运用matlab画x-y图
  • ¥15 用idea运行项目,运行tomcat报错:断言失败
  • ¥15 Sqlserver查询链接服务器数据问题
  • ¥15 Bibtex4Word 引用中文文献
  • ¥20 用opencv c/c++ 转换成灰度图,然后做一下直方图均衡,输出mp4文件