[Vssue]kamacoder/0108.冗余连接.md

[youngyangyang04]

https://www.programmercarl.com/kamacoder/0108.%E5%86%97%E4%BD%99%E8%BF%9E%E6%8E%A5.html

[ckd0817]

这样找出来的不应该是第一条可以删除的边吗，而题目要求的是最后一条可以删除的边

[DEZREMNACUI]

n个边，n个点，那我无脑删最后出现的一条变不就一定变成树了吗，笑死

[zgwd666]

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

for _ in range(n):
    s,t=map(int,input().split())
    if isSame(s,t):
        print(str(s)+' '+str(t))
    else:
        join(s,t)

[RowenaHe]

@DEZREMNACUI

n个边，n个点，那我无脑删最后出现的一条变不就一定变成树了吗，笑死

不一定，只有整棵树形成一个大环才是无脑删最后一个。而实际上很可能是一个小环包含在边列表中间部分

[zgwd666]

您发给我的信件已经收到。我会尽快给您回复。

[RowenaHe]

@ckd0817

这样找出来的不应该是第一条可以删除的边吗，而题目要求的是最后一条可以删除的边

题目中只存在一个环。这样的算法出来的是构成一个环的最后一条边，就是题目指定的最后一条可删除边

[XuxingDaily]

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        DisJoin dj = new DisJoin(1001);
        
        int n = sc.nextInt();
        // 对每条边，只要重复加入到一个集合中了，就说明是冗余了
        for (int i = 0; i < n; i++) {
            int s = sc.nextInt(), t = sc.nextInt();
            if (dj.isSame(s, t)) {
                System.out.println(s + " " + t);
            }
            dj.join(s, t);
        }
    }
}

class DisJoin {
    private int[] farther;
    
    public DisJoin(int N) {
        farther = new int[N];
        for (int i = 0; i < N; i++) {
            farther[i] = i;
        }
    }
    
    public int find(int n) {
        return n == farther[n] ? n : (farther[n] = find(farther[n]));
    }
    
    public boolean isSame(int a, int b) {
        a = find(a);
        b = find(b);
        return a == b;
    }
    
    public void join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            farther[b] = a;
        }
    }
}

[jing-1196]

@ckd0817

这样找出来的不应该是第一条可以删除的边吗，而题目要求的是最后一条可以删除的边

冗余边只有一条哦，所以第一个出现的就是最后使得冗余的那条边，即符合题意的。

[zgwd666]

您发给我的信件已经收到。我会尽快给您回复。

[zgwd666]

您发给我的信件已经收到。我会尽快给您回复。

[1137043480]

您的邮件已收到，谢谢

[1137043480]

import java.util.*;

public class Main {
public static void main(String[] args) {
int N;
Scanner scanner = new Scanner(System.in);

    // 读取 N 的值
    N = scanner.nextInt();
     // 创建 DisJoint 对象
    DisJoint father = new DisJoint(N+1);
    
    for (int i=0;i<N;i++) {
        // 读取两个边
        int s = scanner.nextInt();
        int t = scanner.nextInt();
        if (father.isSame(s,t)) {
            System.out.println(s+" "+t);
        }
        else {
            father.join(s,t);
        }
    }
    
}

}

class DisJoint {
private int[] father;

public DisJoint(int N) {
    father = new int[N];
    for (int i=0;i<N;i++) {
        father[i]=i;
    }
}

public int find(int n) {
    if (n ==father[n]) {
        return n;
    }
    else {
        father[n] = find(father[n]); 
        return father[n];
    }
}

public void join(int n, int m) {
    n = find(n);
    m = find(m);
    if (n==m) return;
    father[n] = m;
}

public boolean isSame(int n,int m) {
    n = find(n);
    m = find(m);
    return n==m;
}

}