Submission #449340

---

Source Code Expand

#include <iostream>
#include <map>
#include <vector>
#include <set>

using namespace std;

int m, n;
multimap<int, int> relations;
set<int> unvisited;

int main()
{
    cin >> n;
    cin >> m;
    for (int i = 1; i <= n; i++) {
        unvisited.insert(i);
    }
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        relations.insert(make_pair(x, y));
    }

    int max_cluster_size = 0;
    while (!unvisited.empty()) {
        int cluster_size = 1;
        auto p = unvisited.begin();
        unvisited.erase(p);

        auto it_range = relations.equal_range(*p);
        for (auto it = it_range.first; it != it_range.second; ++it) {
            auto pp = unvisited.find(it->second);
            if (pp != unvisited.end()) {
                unvisited.erase(pp);
                cluster_size++;
            }
        }

        max_cluster_size = max(max_cluster_size, cluster_size);
    }

    cout << max_cluster_size << endl;
}

Submission Info

Judge Result