2015/04/24

【UVa】10608-Friends (disjoint set)



Disjoint set 基礎知識與函式
http://celinechiu0809.blogspot.tw/2015/04/cdisjoint-set-array.html

題目連結

題目大意：
每一筆測資有N個人和M個連結關係。每一個連結(a, b)代表a認識b。若a認識b, b認識c, 則abc同在一個小圈圈裡，算出最大的小圈圈總共有多少人。

解題策略：
本題的解題思路我歷經了三個步驟
1. adjacent matrix + dfs ：N太大，無法建立matrix，放棄。
2. adjacent list + dfs：這個是行得通的，可是送上uva跑卻TLE，list的搜尋太慢，放棄。
3. disjoint set：最後這個是成功的，先把每個人都變成一個set，再union起來，已一個num陣列記錄每一個小圈圈有多少人，最後在num裡最大的即是答案。

Code

?
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
#include <cstdio>
#include <cstdlib>
#define MAX_N 30000
using namespace std;
int set[MAX_N], num[MAX_N], n;
void make_set(){
    for (int i=1; i<=n; i++){
        set[i] = i;
        num[i] = 1;
    }
}
void union_set(int a, int b){
    if (set[a] != set[b]){
        int x = set[a], y =  set[b];
        num[set[a]] = 0;
        for (int i=1; i<=n; i++) {
            if (set[i]==x){
                set[i] = y;
                num[set[b]]++;
            }
        }
    }
}
int main()
{
    int t, m, a, b;
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &m);
        make_set();
        while(m--){
            scanf("%d %d", &a, &b);
            union_set(a, b);
        }
        int max=0;
        for (int i=1; i<=n; i++) {
            if (num[i]>max) max = num[i];
        }
        printf("%d\n", max);
    }
    return 0;
}

這是第二種想法adjacent list + dfs 失敗的code

?
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
#include <cstdio>
#include <cstdlib>
#define MAX_N 30000
using namespace std;
struct dfs{
    int color, adj;
};
int n, maxp, tmpcount;
struct dfs dfs[MAX_N];
int survey(int v, int u, int* node, int* next){
    int x = dfs[v].adj;
    if (x==-1) return 0;
    while (next[x] != -1) {
        if (node[x]==u) return 1;
        x = next[x];
    }
    if (node[x]==u) return 1;
    return 0;
}
void dfs_visit(int v, int* node, int* next){
    tmpcount++;
    dfs[v].color = 1;
    for(int u=1; u<=n; u++){
        if(dfs[u].color==0 && survey(v, u, node, next)==1)
            dfs_visit(u, node, next);
    }
    dfs[v].color = 2;
}
void initiate(int m){
    for(int i=1; i<=n; i++){
        dfs[i].color = 0;
        dfs[i].adj = -1;
    }
    maxp = 0;
}
void build_re(int a, int b, int* node, int* next, int now_in){
    int x = dfs[a].adj;
    if (x == -1){
        dfs[a].adj = now_in;
        node[now_in] = b;
    }
    else{
        while (next[x] != -1)  x = next[x];
        next[x] = now_in;
        node[now_in] = b;
    }
}
int main()
{
    int t, m, a, b, now_in;
    scanf("%d", &t);
    while(t--){
        scanf("%d %d", &n, &m);
        initiate(m);
        int node[2*m], next[2*m];
        for(int i=0; i< 2*m; i++) next[i] = -1;
        now_in = 0;
        while(m--){
            scanf("%d %d", &a, &b);
            build_re(a, b, node, next, now_in);
            now_in++;
            build_re(b, a, node, next, now_in);
            now_in++;
        }
        for (int i=1; i<=n; i++){
            tmpcount = 0;
            if (dfs[i].color == 0) dfs_visit(i, node, next);
            if (tmpcount>maxp) maxp = tmpcount;
        }
        printf("%d\n", maxp);
    }
    return 0;
}

於
標籤： ,