2019年1月22日 星期二

資料結構 C語言 讀入一圖形的資料，然後回答該圖是否為樹 


 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
#include <stdio.h>
#define N 1000

int father[N], rank[N];

void makeset(int x)
{
    father[x] = x;
    rank[x] = 0;
}

int find(int x)
{
    if (x != father[x])    father[x] = find(father[x]);
    return father[x];
}

int Union(int x, int y)
{    x = find(x);
    y = find(y);
    if (x == y)    return 0;
    if (rank[x] > rank[y]) father[y] = x;
    else
    {
        if (rank[x] == rank[y])    rank[y]++;
        father[x] = y;
    }
    return 1;
}

int main(int argc, char const *argv[])
{
    int k = 1;
    int a, b;
    int flag = 0;
    register int i;
    for (i = 0; i < N; i++)    makeset(i);
    while (scanf("%d%d", &a, &b) != EOF && a >= 0 && b >= 0)
    {
        if (!a && !b)
        {
            int cnt = 0;
            for (i = 0; i < N; i++)
                if (father[i] == i && rank[i])
                    cnt++;
            if (cnt > 1)   flag = 1;
            if (!flag)
                printf("Case %d is a tree.\n", k++);
            else
                printf("Case %d is not a tree.\n", k++);
            for (i = 0; i < N; i++)    makeset(i);
            flag = 0;
            continue;
        }
        if (!flag && !Union(a, b))    flag = 1;
    }
    return 0;
    }



 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
#include <stdio.h>
#define N 1000

int father[N], rank[N];

void makeset(int x)
{
    father[x] = x;
    rank[x] = 0;
}

int find(int x)
{
    if (x != father[x])    father[x] = find(father[x]);
    return father[x];
}

int Union(int x, int y)
{    x = find(x);
    y = find(y);
    if (x == y)    return 0;
    if (rank[x] > rank[y]) father[y] = x;
    else
    {
        if (rank[x] == rank[y])    rank[y]++;
        father[x] = y;
    }
    return 1;
}

int main(int argc, char const *argv[])
{
    int k = 1;
    int a, b;
    int flag = 0;
    register int i;
    for (i = 0; i < N; i++)    makeset(i);
    while (scanf("%d%d", &a, &b) != EOF && a >= 0 && b >= 0)
    {
        if (!a && !b)
        {
            int cnt = 0;
            for (i = 0; i < N; i++)
                if (father[i] == i && rank[i])
                    cnt++;
            if (cnt > 1)   flag = 1;
            if (!flag)
                printf("Case %d is a tree.\n", k++);
            else
                printf("Case %d is not a tree.\n", k++);
            for (i = 0; i < N; i++)    makeset(i);
            flag = 0;
            continue;
        }
        if (!flag && !Union(a, b))    flag = 1;
    }
    return 0;
    }
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)