27635: 判断无向图是否连通有无回路(同23163)

http://cs101.openjudge.cn/practice/27635/

例题：给定一个无向图，判断是否连通，是否有回路。

输入

第一行两个整数n,m，分别表示顶点数和边数。顶点编号从0到n-1。 (1<=n<=110, 1<=m <= 10000) 接下来m行，每行两个整数u和v，表示顶点u和v之间有边。

输出

如果图是连通的，则在第一行输出“connected:yes",否则第一行输出“connected:no"。如果图中有回路，则在第二行输出“loop:yes ",否则第二行输出“loop:no"。

样例输入

3 2
0 1
0 2

样例输出

connected:yes
loop:no

来源

http://dsbpython.openjudge.cn/dspythonbook/P1040/

dfs能直接判断是否连通，过程中记录父亲节点，只要当前节点能够去到一个已经遍历过的节点，并且这个节点不是父亲节点，那么必然成环，以及连通和成环是可以同时判断的

python

#王昊 光华管理学院
n, m = list(map(int, input().split()))
edge = [[]for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    edge[a].append(b)
    edge[b].append(a)
cnt, flag = set(), False


def dfs(x, y):
    global cnt, flag
    cnt.add(x)
    for i in edge[x]:
        if i not in cnt:
            dfs(i, x)
        elif y != i:
            flag = True


for i in range(n):
    cnt.clear()
    dfs(i, -1)
    if len(cnt) == n:
        break
    if flag:
        break

print("connected:"+("yes" if len(cnt) == n else "no"))
print("loop:"+("yes" if flag else 'no'))

python

def is_connected(graph, n):
    visited = [False] * n  # 记录节点是否被访问过
    stack = [0]  # 使用栈来进行DFS
    visited[0] = True

    while stack:
        node = stack.pop()
        for neighbor in graph[node]:
            if not visited[neighbor]:
                stack.append(neighbor)
                visited[neighbor] = True

    return all(visited)

def has_cycle(graph, n):
    def dfs(node, visited, parent):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                if dfs(neighbor, visited, node):
                    return True
            elif parent != neighbor:
                return True
        return False

    visited = [False] * n
    for node in range(n):
        if not visited[node]:
            if dfs(node, visited, -1):
                return True
    return False

# 读取输入
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

# 判断连通性和回路
connected = is_connected(graph, n)
has_loop = has_cycle(graph, n)
print("connected:yes" if connected else "connected:no")
print("loop:yes" if has_loop else "loop:no")

这题一个dfs就够了

判断连通就是单纯dfs，每个节点拓展出没去过的节点递归，cnt这个集合记录去过的节点

判断成环可以同步进行，只是我们的dfs需要而外记录一下父亲节点，于是只要当前节点能够去到一个已经遍历过的节点，并且这个节点不是父亲节点，那么必然成环——这是因为我们的dfs是单源的遍历，不妨说那个已经遍历的非父亲节点是x，这次dfs的源头是root，当前节点是cur，那么x一定存在一条不经过cur到达root的路径（因为不会遍历去过的节点，所以cur是第一次到，之前遍历到x一定是没到过cur的），而现在cur能到x，说明有一条经过cur到达root的路径，而且x不是父亲节点，于是这两条路径通过root形成了一个环，并且由于不是父亲节点，所以这个环上的节点数>2，于是就必然是环了——这个想法说实话临时想是有点绕的。

还有一个性质，一旦连通，必然成环也判断完毕了，一旦成环，也意味着连通必然判断完毕了，所以两个break都是正确的。

python

# 熊江凯、元培学院
n,m=list(map(int,input().split()))
edge=[[]for _ in range(n)]
for _ in range(m):
    a,b=list(map(int,input().split()))
    edge[a].append(b)
    edge[b].append(a)
cnt,ok=set(),0
def dfs(x,y):
    global cnt,ok
    cnt.add(x)
    for i in edge[x]:
        if i not in cnt:dfs(i,x)
        elif y!=i:ok=1
for i in range(n):
    cnt.clear()
    dfs(i,-1)
    if len(cnt)==n:break
    if ok:break
print("connected:"+("yes"if len(cnt)==n else "no")+'\n'+"loop:"+('yes'if ok else 'no'))

python

# 2100017777 李鹏辉
# pylint: skip-file

n, m = map(int, input().split())
p = [i for i in range(n)]

def find(i):
    if p[i] != i:
        p[i] = find(p[i])
    return p[i]

def union(x, y):
    p[find(x)] = find(y)

l = False
for _ in range(m):
    x, y = map(int, input().split())
    if find(x) == find(y):
        l = True
    else:
        union(x, y)
p = [find(i) for i in range(n)]
p = set(p)
print('connected:yes' if len(p) == 1 else 'connected:no')
print('loop:yes' if l else 'loop:no')

27635: 判断无向图是否连通有无回路(同23163) ​

27635: 判断无向图是否连通有无回路(同23163)