Tạo bài viết
Đăng ký
02/10/2018, 14:30

Cấu trúc dữ liệu Disjoint Sets

Bài viết này là phần 7 trong 7 bài của Series Lý thuyết đồ thị căn bản Lý thuyết đồ thị căn bản Bài 1: Ma trận kề C++/Pascal Lý thuyết đồ thị Bài 2: Danh sách cạnh C++ Lý thuyết đồ thị Bài 3: Danh sách kề C++ Lý thuyết đồ thị Bài 4: Thuật toán tìm kiếm theo chiều sâu DFS ...

Bài viết này là phần 7 trong 7 bài của Series Lý thuyết đồ thị căn bản

Lý thuyết đồ thị căn bản
  • Bài 1: Ma trận kề C++/Pascal Lý thuyết đồ thị
  • Bài 2: Danh sách cạnh C++ Lý thuyết đồ thị
  • Bài 3: Danh sách kề C++ Lý thuyết đồ thị
  • Bài 4: Thuật toán tìm kiếm theo chiều sâu DFS pascal c++
  • Bài 5: Thuật toán tìm kiếm theo chiều rộng BFS pascal c++
  • Bài 6: Thuật toán loang trên ma trận
  • Cấu trúc dữ liệu Disjoint Sets

Nguồn đề bài: http://www.spoj.com/KSTN/problems/DS2509/

1. Đề bài Cấu trúc dữ liệu Disjoint Sets

Disjoint-set hiểu 1 cách đơn giản là 1 cách lưu trữ các tập hợp phần tử của 1 tập lớn cho trước.

Các phép toán thường được quan tâm tới trong disjoint-set là:

MakeSet(i): tạo ra 1 tập chỉ có i.

FindSet(i): tìm tập hợp mà nút i thuộc.

Union(i,j): ghép 2 tập hợp chứa i và j với nhau.

Xét bài toán:

Cho 1 đồ thị gồm N đỉnh được đánh số từ 1 đến N, giữa 2 đỉnh bất kỳ đều có thể nối hoặc không nối với nhau. Ở trạng thái ban đầu tất cả các đỉnh đều không có cạnh nối.

Bạn được cho một số yêu cầu, trong đó mỗi yêu cầu có 2 dạng:

Union(x, y): X Y 1 có ý nghĩa là bạn cần nối 2 đỉnh X và Y.

Find(x, y): X Y 2 có ý nghĩa là bạn cần cho biết với trạng thái như hiện tại thì 2 đỉnh X và Y có thuộc cùng một thành phần liên thông hay không? Hai đỉnh được coi là thuộc cùng một thành phần liên thông nếu có đường đi từ đỉnh này đến đỉnh kia qua 1 số đỉnh khác và 2 đỉnh liên tiếp trên đường đi đều có cạnh nối.

Input

Dòng đầu tiên ghi một số nguyên dương P là số yêu cầu.

Trong P dòng tiếp theo, mỗi dòng ghi ba số nguyên dương X, Y, Z với ý nghĩa có yêu cầu loại Z với 2 đỉnh X và Y.

Output

Với mỗi yêu cầu dạng X Y 2 (với Z = 2) bạn cần ghi ra số 0 hoặc 1 trên 1 dòng tùy thuộc 2 đỉnh X và Y không thuộc hoặc thuộc cùng một thành phần liên thông.

Example

Input:
9
1 2 2
1 2 1
3 7 2
2 3 1
1 3 2
2 4 2
1 4 1
3 4 2
1 7 2

Output:
0
0
1
0
1
0

Giới hạn:
1 ≤ N ≤ 10000
1 ≤ P ≤ 50000

2. Code Disjoint Sets (Pascal và C++):

a. Code pascal

const fi='; fo='; maxn=round(1e4+1); var cha:array[0..maxn] of longint; function goc(u:longint):longint; begin while cha[u]>0 do u:=cha[u]; exit(u); end; procedure union(u,v:longint); var x:longint; begin x:=cha[u]+cha[v]; if cha[u]>cha[v] then begin cha[u]:=v; cha[v]:=x; end else begin cha[v]:=u; cha[u]:=x; end; end; procedure main; var f,g:Text; q,qn:longint; u,v,r1,r2,yc:longint; begin assign(f,fi); reset(f); assign(g,fo); rewrite(g); readln(f,qn); fillchar(cha,sizeof(cha),255); for q:=1 to qn do begin readln(f,u,v,yc); r1:=goc(u); r2:=goc(v); if yc=1 then if r1<>r2 then union(r1,r2) else else writeln(g,ord(r1=r2)); end; close(f); close(g); end; begin main; end.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
const   fi=';
        fo=';
        maxn=round(1e4+1);
 
var     cha:array[0..maxn] of longint;
 
function goc(u:longint):longint;
begin
        while cha[u]>0 do u:=cha[u];
        exit(u);
end;
 
procedure union(u,v:longint);
var     x:longint;
begin
        x:=cha[u]+cha[v];
        if cha[u]>cha[v] then
                begin
                        cha[u]:=v;
                        cha[v]:=x;
                end
        else
                begin
                        cha[v]:=u;
                        cha[u]:=x;
                end;
end;
 
procedure main;
var     f,g:Text;
        q,qn:longint;
        u,v,r1,r2,yc:longint;
begin
        assign(f,fi); reset(f); assign(g,fo); rewrite(g);
        readln(f,qn);
        fillchar(cha,sizeof(cha),255);
        for q:=1 to qn do
                begin
                        readln(f,u,v,yc);
                        r1:=goc(u); r2:=goc(v);
                        if yc=1 then
                                if r1<>r2 then union(r1,r2)
                                else
                        else
                                writeln(g,ord(r1=r2));
                end;
        close(f); close(g);
end;
 
begin
        main;
end.

b. Code c++

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <set> #define FOR(i,a,b) for(int i=a; i<=b; i++) #define FO(i,a,b) for(int i=a; i<b; i++) #define pb push_back #define LL long long using namespace std; inline int nextInt(){ int x = 0; register int c = getc(stdin); int sign = 0; for( ; ((c < 48 || c > 57) && c != '-'); c = getc(stdin)); if(c == '-'){ sign = 1; c = getc(stdin); } for( ; c > 47 && c < 58; c = getc(stdin)) x = (x<<1) + (x<<3) + c - 48; if (sign) x = -x; return x; } inline LL nextLong(){ LL x = 0; register int c = getc(stdin); int sign = 0; for( ; ((c < 48 || c > 57) && c != '-'); c = getc(stdin)); if(c == '-'){ sign = 1; c = getc(stdin); } for( ; c > 47 && c < 58; c = getc(stdin)) x = (x<<1) + (x<<3) + c - 48; if (sign) x = -x; return x; } void scan(long &x){ x = nextLong(); } long n,p[50001],x,y,c; long findset(long i) { if (p[i] == 0 ) return i; // neu i la goc p[i] = findset(p[i]); return p[i]; } void Union(long x, long y) { long u,v; u = findset(x);// tim goc x v = findset(y);// tim goc y if (u==v) return; // cung goc if (p[u] < p[v]) { // u nhieu con hon v p[u]+=p[v]; p[v] = u; // noi nhanh v vao u } else { p[v]+=p[u]; p[u] = v; } } main() { scan (n); //FOR (i,1,10000) p[i] = -1; while(n--) { scan(x);scan(y);scan(c); if (c == 1) Union(x,y); if (c == 2) if (findset(x)==findset(y)) printf ("1n"); else printf ("0n"); } }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define FO(i,a,b) for(int i=a; i<b; i++)
#define pb push_back
#define LL long long
using namespace std;
 
inline int nextInt(){
    int x = 0;
    register int c = getc(stdin);
    int sign = 0;
    for( ; ((c < 48 || c > 57) && c != '-'); c = getc(stdin));
    if(c == '-'){
        sign = 1;
        c = getc(stdin);
    }
    for( ; c > 47 && c < 58; c = getc(stdin)) x = (x<<1) + (x<<3) + c - 48;
    if (sign) x = -x;
    return x;
}
 
inline LL nextLong(){
    LL x = 0;
    register int c = getc(stdin);
    int sign = 0;
    for( ; ((c < 48 || c > 57) && c != '-'); c = getc(stdin));
    if(c == '-'){
        sign = 1;
        c = getc(stdin);
    }
    for( ; c > 47 && c < 58; c = getc(stdin)) x = (x<<1) + (x<<3) + c - 48;
    if (sign) x = -x;
    return x;
}
 
void scan(long &x){
    x = nextLong();
}
 
long n,p[50001],x,y,c;
 
long findset(long i) {
    if (p[i] == 0 ) return i; // neu i la goc
    p[i] = findset(p[i]);
    return p[i];
}
 
void Union(long x, long y) {
    long u,v;
    u = findset(x);// tim goc x
    v = findset(y);// tim goc y
    if (u==v) return; // cung goc
 
    if (p[u] < p[v]) { // u nhieu con hon v
        p[u]+=p[v];
        p[v] = u; // noi nhanh v vao u
    }
    else {
        p[v]+=p[u];
        p[u] = v;
    }
}
 
main() {
    scan (n);
    //FOR (i,1,10000) p[i] = -1;
    while(n--) {
        scan(x);scan(y);scan(c);
        if (c == 1)
            Union(x,y);
        if (c == 2)
            if (findset(x)==findset(y))
                printf ("1n");
            else
                printf ("0n");
    }
}

Cấu trúc dữ liệu Disjoint Sets, cau truc du lieu disjoint sets

Vũ Văn Thanh

12 chủ đề

2597 bài viết

Có thể bạn quan tâm
0
Các chủ đề đang được quan tâm
phần mềm lập trình php | lập trình web php + mysql | khóa học lập trình php | tự học lập trình php | học php cơ bản thachpham | Code24h | Cho thuê phòng trọ hà nội | Cho thuê phòng trọ bình thạnh | Cho thuê phòng trọ | Cho thuê nhà trọ
Đăng ký

Đăng ký nhận thông báo

Các bài học thú vị sẽ được gửi đến inbox của bạn

HỖ TRỢ HỌC VIÊN
VỀ CODE24H
HỢP TÁC VÀ LIÊN KẾT
KẾT NỐI VỚI CHÚNG TÔI
TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI

CCode 24h, code mọi lúc, mọi nơi

© Copy right 2018 - 2024