import sys
def get_all_edges(tri):
a, b, c = tri[0], tri[1], tri[2]
return [(a, b), (b, c), (c, a)]
def build_right_pair_from_edges(tri):
min_index = tri.index(min(tri))
return tri[min_index:] + tri[:min_index]
def edges_exist(edges, valid_edges):
for i, edge in enumerate(edges):
if edge in valid_edges:
return 1, i
elif tuple(reversed(edge)) in valid_edges:
return 0, i
else:
continue
return -1, None
def find_right_dirs(tris):
tris = [[tri, i] for i, tri in enumerate(tris)]
valid_edges, res, tri0 = [], [], tris[0]
valid_edges.extend(get_all_edges(tri0[0]))
res.append([build_right_pair_from_edges(tri0[0]), 0])
tris.pop(0)
while len(tris):
tri = tris[0]
edges = get_all_edges(tri[0])
code, loc = edges_exist(edges, valid_edges)
if code == 0:
edges.pop(loc)
valid_edges.extend(edges)
res.append([build_right_pair_from_edges(tri[0]), tri[1]])
tris.pop(0)
elif code == 1:
tris.pop(0)
tris.append([list(reversed(tri[0])), tri[1]])
else:
tris.pop(0)
tris.append(tri)
res.sort(key=lambda x: x[1])
return [_[0] for _ in res]
if __name__ == "__main__":
# N, M = list(map(int, input().split()))
# tris = []
# for i in range(M):
# tris.append(list(map(int, input().split())))
N, M = 6, 4
tris = [[3, 2, 4],[1, 3, 2],[3, 6, 5],[5, 3, 4]]
res = find_right_dirs(tris)
for _ in res:
print(_[0], _[1], _[2])
ac了，思路就是以第一个三角形为基准，将合法的双顶点边放到一个列表a中，对于每一个新来的三角形，会出现两种情况：
1. 新的三角形没有双顶点边在a中，这个可以先跳过，延后再算；
2. 新的三角形在a中可以找到双顶点边 (<a, b>与<a, b>、<a, b>与<b, a>)，这种就是可以继续计算的，如果边的方向不同 (<a, b>、<b, a>)，这个新三角形的朝向就是对的，直接将整个pair放入结果列表res中 (还要排序)，同时更新列表a；如果边的方向相同 (<a, b>、<a, b>)，朝向就相反了，将这个pair翻转后，再重新计算；最后当所有的pair都被计算了，就结束了。
关于为什么同向边朝向反了，反向边朝向正确，可以画个图就看出来了~
