Skip to content

14082: 【原4082】四通八达

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4082

Description

古老的亚平宁半岛上,分布着许许多多彼此独立的国家,每个国家又由大大小小的城池组成。现在,每个国家内部的城市之间都是互相可以到达的,而国家与国家之间相互敌视, 没有任何一条道路链接起两个不同国家的城市。
为了完善国内交通路网,阔绰的国王们打算修路,使得每个国家内任意两个城市间都有一条道路直接相连。
旅行家帕帕迪只记得所有道路的信息,他想据此计算一下这些国家一共需要多修多少条路。

Input Format

第一行给出两个整数n,m:n表示共有 n + 1 个城市,依次编号0到n,m代表现有道路条数。
接下来m行,每行两个整数a,b,代表城市a与b间存在一条道路。

Output Format

一个数R,代表需要修建道路的数目

Sample Input

6 3  
0 4  
1 2  
2 4

Sample Output

3

FineArtz's solution

/* 四通八达 */
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

class edge{
public:
    edge(int xx, int yy) : x(xx), y(yy) {}
    int x = 0, y = 0;
};

int parent[1000005];
int v[1000005] = {0};
vector<edge> e;
map<int, set<int>> ee;
int n, m, cnt = 0;
long long ans;

int find(int x){
    while (parent[x] != x){
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

int main(){
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        int x, y;
        cin >> x >>y;
        if (x == y) continue;
        if (ee.find(x) != ee.end()){
            if (ee[x].find(y) != ee[x].end())
                continue;
        }
        ++cnt;
        e.emplace_back(x, y);
        ee[x].insert(y);
        ee[y].insert(x);
    }
    for (int i = 0; i <= n; ++i)
        parent[i] = i;
    for (auto i : e){
        int p = find(i.x);
        int q = find(i.y);
        if (p != q)
            parent[p] = q;
    }
    for (int i = 0; i <= n; ++i)
        parent[i] = find(i);
    for (int i = 0; i <= n; ++i)
        ++v[parent[i]];
    for (int i = 0; i <= n; ++i){
        if (v[i] != 0){
            ans += v[i] * (v[i] - 1) / 2;
        }
    }
    cout << ans - cnt << endl;
    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

const int maxN = 1e6;

struct edgeNode {
    int data;
    edgeNode *next;

    edgeNode(int d = 0, edgeNode *n = 0) : data(d), next(n) {}
};

struct verNode {
    int data;
    edgeNode *head;
    int degree;

    verNode(int d = 0, edgeNode *h = 0) : data(d), head(h), degree(0) {}
};

int N, M, ans = 0, city = 0, degree = 0;
verNode *nodes[maxN];
bool isVisited[maxN] = {0};

void DFS(int);

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    for (int i = 0; i <= N; i++) {
        nodes[i] = new verNode(i);
    }

    for (int i = 0; i < M; i++) {
        int temp1, temp2;

        cin >> temp1 >> temp2;

        nodes[temp1]->head = new edgeNode(temp2, nodes[temp1]->head);
        nodes[temp1]->degree++;
        nodes[temp2]->head = new edgeNode(temp1, nodes[temp2]->head);
        nodes[temp2]->degree++;
    }

    for (int i = 0; i <= N; i++) {
        if (!isVisited[i]) {
            city = degree = 0;
            DFS(i);
            ans += ((city * (city - 1)) - degree) / 2;
        }
    }

    cout << ans;

    return 0;
}

void DFS(int i) {
    isVisited[i] = 1;
    city++;
    degree += nodes[i]->degree;

    edgeNode *p = nodes[i]->head;

    while (p) {
        if (!isVisited[p->data]) {
            DFS(p->data);
        }
        p = p->next;
    }
}