【代码随想录算法训练营第六十二天|卡码网108.冗余连接、109.冗余连接II】

108.冗余连接

就是对输入进来的边判断是否在一个并查集中，在的话就把这个删除了，不再就加入并查集中。

n = int(input())
father = [0] * (n+1)
def init():
    for i in range(n+1):
        father[i] = i
        
def find(u):
    if father[u] != u:
        father[u] = find(father[u])
    return father[u]
    
def isSame(u, v):
    u = find(u)
    v = find(v)
    return u == v

def join(u, v):
    u = find(u)
    v = find(v)
    if u != v:
        father[v] = u
init()
for i in range(n):
    s, t = map(int, input().split())
    if isSame(s, t):
        print(str(s)+' '+str(t))
    else:
        join(s, t)

109.冗余连接II

上一题的图是一个无向图，因此只需要把最后会导致成环的那个边删除即可。这一题则会有两种情况，第一种是出现一个结点有两个入度，这是题目所不允许出现的情况，还有一种就是和上题一样入度都为1但是出现了环的情况。
如果有一个结点入度为2，那么就一定是在这两个入的边中挑一条删除，然后看剩下的结点中是否还会出现环，如果还出现环说明删错了，应该删除另一个；反之亦然。
因此在输入边的时候需要对每一个结点的入度进行统计，所有边输入进来之后，对所有边的入的结点判断是否入度为2，是的话则把这个边拿出来。因为题目要求优先删除后加入的边，所以先把后加入的边按照上述逻辑进行判断。
如果没有入度为2的结点，那就是按照上一题的方法进行删除。

n = int(input())
father = [i for i in range(n+1)]

def find(u):
    if father[u] != u:
        father[u] = find(father[u])
    return father[u]

def isSame(u, v):
    u = find(u)
    v = find(v)
    return u == v

def join(u, v):
    if not isSame(u, v):
        father[v] = u
    
def removeEdge(edges):
    for edge in edges():
        if isSame(edge[0], edge[1]):
            print(str(edge[0])+ ' '+str(edge[1]))
            return
        else:
            join(edge[0], edge[1])

def isTreeAftherRemove(edges, index):
    for i in range(n):
        if i == index:
            continue
        if isSame(edges[i][0], edges[i][1]):
            return False
        else:
            join(edges[i][0], edges[i][1])
    return True
    
edges = []   
inner = [0] * (n+1)
for i in range(n):
    edge = list(map(int, input().split()))
    edges.append(edge)
    inner[edge[1]] += 1
vec = []
for i in range(n):
    if inner[edges[i][1]] == 2:
        vec.append(i)
if vec:
    if isTreeAftherRemove(edges, vec[1]):
        print(str(edges[vec[1]][0])+' '+str(edges[vec[1]][1]))
    else:
        print(str(edges[vec[0]][0])+ ' '+str(edges[vec[0]][1]))
else:
    removeEdge(edges)