首页 > itarticle > union

union

admin 12月 04, 2020 0

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 

public void (){
    int[] friends = new int[n];
    for (int i = 0; i < n; i++) friends[i] = i;
}

public int find(int i){
    if (friends[i] != i) friends[i] = find(friends[i]);
    return friends[i];
}

public void union(int i, int j){
    int si = find(i);
    int sj = find(j);
    if (si != sj) friends[si] = sj;
}

MakeSet

1
2
3
 
def makeSet(a, n):
    for i in range(n):
        a[i] = i

Find

1
2
3
4
5
6
 
def find(i):
    global a
    if a[i] != i:
        
        a[i] = find(a[i]) 
    return a[i]

Union

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
def union(x, y):
    fx = find(x)
    fy = find(y)

    if (fx == fy):
        return

    global rank
    global a
    # Optimation 2: Union by Rank
    if (rank[fx]>rank[fy]):
        a[fy] = fx
    else:
        a[fx] = fy
        if (rank[fx] == rank[fy]):
            rank[fy] += 1

Example problem

Description

If a family is too large, it’s really not easy to judge whether two people are relatives. Give a relatives diagram and find out whether any given two people have relatives. Provisions: X and y are relatives, y and Z are relatives, then x and Z are relatives. If X and y are relatives, then x’s relatives are relatives of y, and y’s relatives are relatives of X.

Input

The first line: three integers n, m, p, (n <= 5000, m <= 5000, P <= 5000), respectively, denote n individuals and m relatives, and ask P about their relatives.

The following M lines: Mi, Mj, 1 <= Mi, Mj <= N, two numbers per line, indicating that Mi and Mj are related.

Next, line p: Pi and Pj are two numbers per line. Ask if Pi and Pj are related.

Output

P lines, one’Yes’or’No’ per line. The answer to the $i^{th}$ question is “have” or “don’t have” relatives.

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能