Submission #5018384

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#define llong long long
#define INF (__INT32_MAX__ / 2)

using namespace std;


class DisjointSets {
    class Node {
        public: 
        int parent = -1;
        int rank = 0;
        int degree = 1;
    };
    
private:
    Node *nodes;

    void make_set(int x) {
        nodes[x].parent = x;
        nodes[x].rank = 0;
        nodes[x].degree = 1;
    }

    int find_set(int x) {
        if(nodes[x].parent == x)
            return x;

        //経路圧縮
        nodes[x].rank = 0;
        return nodes[x].parent = find_set(nodes[x].parent);
    }

public:
    DisjointSets(){}
    DisjointSets(int length) {
        nodes = (Node *)malloc(sizeof(Node) * length);

        for(int i = 0; i < length; ++i)
            make_set(i);
    }

    ~DisjointSets() {
        free(nodes);
    }

    int degree(int x) {
        return nodes[find_set(x)].degree;
    }

    void unite(int x, int y) {
        if(nodes[x].rank < nodes[y].rank) {
            nodes[find_set(x)].parent = find_set(y);
            nodes[y].degree += nodes[x].degree;
        } else if(nodes[x].rank > nodes[y].rank) {
            nodes[find_set(y)].parent = find_set(x);
            nodes[x].degree += nodes[y].degree;
        } else {
            nodes[find_set(y)].parent = find_set(x);
            nodes[x].rank++;
            nodes[x].degree += nodes[y].degree;
        }
    }

    bool same(int x, int y) {
        int set_x = find_set(x);
        int set_y = find_set(y);
        return set_x == set_y;
    }
};

int main(int argc, char **argv) {
    int n, k;
    cin >> n >> k;

    int res = 1;
    DisjointSets *p_sets = new DisjointSets(n);
    for(int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        p_sets->unite(x - 1, y - 1);
        res = max(res, p_sets->degree(x - 1));
    }
    
    cout << res << endl;
}

Submission Info

Judge Result