2025年国际信息学奥林匹克竞赛编程试题：算法竞赛中的图论算法挑战

一、编程题

要求：实现一个程序，该程序能够读取一个无向图，并判断该图是否为连通图。如果图是连通的，则输出连通；如果图不是连通的，则输出不连通。输入图由多行表示，第一行是顶点数和边数，接下来每行表示一条边，边的两个顶点用空格隔开。

输入：

56

12

23

34

45

51

25

输出：

连通

输入：

44

12

23

34

41

输出：

不连通

二、判断题

要求：判断以下说法的正误。

1.在图论中，有向图和无向图的最大区别在于边的方向性。

2.在无向图中，任意两个顶点之间都存在一条路径。

3.欧拉