URAL 1272. Non-Yekaterinburg Subway

Author: 2015-08-22

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1272

1272. Non-Yekaterinburg Subway

Time limit: 1.0 second
Memory limit: 64 MB
A little town started to construct a subway. The peculiarity of the town is that it is located on small islands, some of them are connected with tunnels or bridges. The mayor is sure that the subway is to be under the ground, that’s why the project must use the less bridges the better. The only request for the subway is that the townsmen could get by metro (may be with changes) from every island to every island. Fortunately, we know that there is enough tunnels and bridges for it. It was decided to construct as less passages from island to island as possible to save money.
Your task given a town plan to determine the minimal possible number of bridges that is necessary to use in the subway construction.

Input

The first line contains three integers separated with a space: N (the number of islands, 1 ≤ N ≤ 10000), K (the number of tunnels, 0 ≤ K ≤ 12000) and M (the number of bridges, 0 ≤ M ≤ 12000). Then there are K lines; each line consists of two integers — the numbers of islands, connected with the corresponding tunnel. The last M lines define bridges in the same format.

Output

the minimal number of bridges necessary for the subway construction.

Sample

input output 
6 3 4
1 2
2 3
4 5
1 3
3 4
4 6
5 6
 
2
Problem Author: Magaz Asanov (prepared Igor Goldberg)
Problem Source: Ural State University championship, October 25, 2003

2. 思路

现有若干小岛，岛之间有一些隧道和桥梁，要利用隧道修地铁，求最少还需要多少桥梁，才能让所有岛都相互可达。题目描述得不是很清楚，其实就是把所有的隧道都用来修地铁，如果不能保证所有岛都相互可达，则需要考虑使用桥梁来连通一些岛，求所需桥梁的最少数量。

因为题目中已经明确使用所给的隧道和桥梁，能够保证所有岛都相互可达，则输入数据中给出的桥梁并没有什么用，题目肯定是有解的。读完所有隧道后，并查集查找连通子图个数，减1即得所需桥梁数量。

3. 代码

#include <stdio.h>
#include <string.h>

#define MAX_N 10005

void solveE2c();
void printArray(int array[], int len);

int main(void) {
    solveE2c();
    return 0;
}


int group[MAX_N + 1];
void solveE2c() {
    int n, k, m, tunnelCnt, groupCnt, groupIdCnt, src, dest, srcGroupId, destGroupId, i;

    memset(group, 0, sizeof(int) * (MAX_N + 1));
    scanf("%d %d %d", &n, &k, &m);

    tunnelCnt = k;
    groupCnt = 0;
    groupIdCnt = 0;
    while (tunnelCnt--) {
        scanf("%d %d", &src, &dest);
        srcGroupId = group[src];
        destGroupId = group[dest];
        if (srcGroupId != 0) {
            if (destGroupId != 0 && destGroupId != srcGroupId) {
                for (i = 1; i <= n; ++i) {
                    if (group[i] == destGroupId) {
                        group[i] = srcGroupId;
                    }
                }
                --groupCnt;
            } else {
                group[dest] = srcGroupId;
            }
        } else if (destGroupId != 0) {
            group[src] = destGroupId;
        } else {
            ++groupCnt;
            ++groupIdCnt;
            group[src] = groupIdCnt;
            group[dest] = groupIdCnt;
        }
        // printArray(group, n);
    }

    for (i = 1; i <= n; ++i) {
        if (group[i] == 0) {
            ++groupCnt;
        }
    }

    printf("%d\n", groupCnt - 1);
}


void printArray(int array[], int len) {
    int i;

    for (i = 1; i <= len; ++i) {
        printf("%d", array[i]);
    }
    printf("\n");
}