1 Star 1 Fork 0

bensonrachel/Atcoder_algorithm

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
D - Pair of Balls(图论+建模+拓扑排序).py 3.15 KB
一键复制 编辑 原始数据 按行查看 历史
# -*- coding: utf-8 -*-
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/9/9
# @File : D - Pair of Balls(图论+建模+拓扑排序).py
# https://atcoder.jp/contests/abc216/tasks/abc216_d
from collections import deque
def create_indegree():
"""
建立每个节点的入度数组,数组在做拓扑排序的过程中会不断变化。
:return:
"""
for u in table:
for v in u:
indegree[v] += 1
def topsort():
"""
进行拓扑序列的建立,也就做一个拓扑排序出来
:return: 拓扑序列的长度(即可以删掉的个数,如果不等于n那就说明No了)
"""
Q = deque([i for i in range(1, n + 1) if indegree[i] == 0])#入度为0的入队
tp = []
while Q:
u = Q.pop()#出队顺序无所谓,拓扑排序不唯一
tp.append(u)#加入到拓扑序列记录数组中
for v in table[u]:#所有以u为尾的边指向的节点的入度都要减一,有向边没箭头那端为尾
indegree[v] -= 1
if indegree[v] == 0:#新的变成了入度为0的入队
Q.append(v)
return len(tp)
"""
先建立邻接表。每种颜色转化成一个点。模型建的不完整搞了一天!!!模型缺了一部分。
只想到想拿第二个就一定要先拿掉第一个,但是没考虑到想拿第三个就要必须拿掉第二个。所以一个圆柱里的数是拓扑的。所以不要直接拿圆柱当邻接表!
216题解:https://www.cnblogs.com/ooctober/p/15218166.html 是看这个代码顿悟的。
建模过程,每次要拿掉最上面两个颜色相同的,就代表其实这种颜色是入度为零的,因为没有任何其他颜色指向这种颜色,因为这种颜色的两个球都在最顶,都是指别人。
"""
if __name__ == '__main__':
n, m = map(int, input().split())
table = [list() for i in range(n + 1)]
#建表过程:
for i in range(m):
k = int(input())
pre = 0#起点
for j in input().split():
if pre != 0:#第一轮循环不会进入这个if。
table[pre].append(int(j))
pre = int(j)#下一个变为起点
"""
那昨天你只建一层图也只差一个样例就过了?
错误的例子:直接除了圆柱第一个后面的直接加进去邻接表。
k = int(input())
a = [int(j) for j in input().split()]
table[a[0]] += (a[1:])
这样就等于只有第一个点到后面的各个点的边,然后后面的点之间就没有关系,这样是错误的,建模没建完整,没考虑到想拿第三个就要必须拿掉第二个,并以此类推的。一个圆柱其实一个图的形状是单链表的图。
所以圆柱的样子并不能直拿来当邻接表!
重边是这样:1 2
:1 2 这样1这个点就有两条边指向2
自环是这样:1 1 这样1就有一条边指向1(自己)
这两个细节都不是代码出问题的地方。
"""
indegree = [0] * (n + 1)
create_indegree()#建立存着每个节点的入度的数组
ans = topsort()
if (ans == n):
print("Yes")
else:
print("No")
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/bensonrachel/atcoder_algorithm.git
git@gitee.com:bensonrachel/atcoder_algorithm.git
bensonrachel
atcoder_algorithm
Atcoder_algorithm
master

搜索帮助