For Offersssss! （Linux与Python篇）

ACM 模式下的 python

模板

万能输入语句：

1	`map(lambda x: int(x), input().split())`

class Solution:
    
    def Function(self, ...):
    	print(...)
    	return

if __name__=="__main__":
	# 单行输入两个数
    n, m = map(lambda x: int(x), input().split())
    
    # m行输入，保存为列表即可
    lst = []
    for i in range(m):
        lst.append(list(map(lambda x: int(x), input().split())))

    # 输出
    Solution().Function(...)

以下为举例：【模板】拓扑排序

描述

给定一个包含 $n$ 个点 $m$ 条边的有向无环图，求出该图的拓扑序。若图的拓扑序不唯一，输出任意合法的拓扑序即可。若该图不能拓扑排序，输出 $−1$。
输入描述：
第一行输入两个整数 $n,m(1 \leq n,m \leq 2 \times 10^{5})$，表示点的个数和边的条数。
接下来的 $m$ 行，每行输入两个整数 $u_{i},v{i}(1 \leq u,v \leq n)$，表示 $u_{i}$ 到 $v_{i}$ 之间有一条有向边。
输出描述：
若图存在拓扑序，输出一行nn个整数，表示拓扑序。否则输出-1−1。

示例1
输入：
5 4
1 2
2 3
3 4
4 5
输出：
1 2 3 4 5

class Solution:
    
    def TopologicalSort(self, n, m, edges):
        indegrees = [0]*(n+1)
        visited = [0]*(n+1)
        dst = [[] for _ in range(n+1)]
        path = []
        queue = []
        for edge in edges:
            indegrees[edge[1]] += 1
            dst[edge[0]].append(edge[1])
        for node in range(1, n+1):
            if indegrees[node] == 0:
                path.append(node)
                visited[node] = 1
                queue.append(node)
        
        while queue:
            node = queue.pop(0)
            for d in dst[node]:
                if not visited[d]:
                    queue.append(d)
                indegrees[d] -= 1
                if not indegrees[d]:
                    path.append(d)
                    visited[d] = 1
        # 输出
        for i in range(n):
            print(path[i], end=' ')
        return


if __name__=="__main__":
	# 单行输入
    n, m = map(lambda x: int(x), input().split())
    
    # 多行输入
    edges = []
    for i in range(m):
        edges.append(list(map(lambda x: int(x), input().split())))

    # 输出
    Solution().TopologicalSort(n, m, edges)