ADS - Quảng cáo

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 2200;
using namespace std;

struct dsu {
    int lab[N];
    int root(int u)
        {return lab[u] <= 0 ? u : (lab[u] = root(lab[u]));}
    void join(int u, int v) {
        if (lab[u] > lab[v]) swap(u, v);
        if (lab[u] == lab[v]) lab[u]--;
        lab[v] = u;
    }
} DS;
int n, m;

int main() {
    ios :: sync_with_stdio(0);
    cin >> n >> m;
    int ans = m, u, v;
    FOR(i, 0, m) {
        cin >> u >> v;
        int x = DS.root(u), y = DS.root(v);
        if (x != y) {DS.join(x, y); ans--;};
    }
    cout << ans;
    return 0;
}

Download