Codeforces Round #376 (Div. 2) C. Socks 并查集+贪心、图论

Source

My Solution

并查集+贪心、图论

在读入的时候直接把有边相连的点维护到一个集合里，最后对于处理出的森林，可以用map<int, map<int, int> > mp;维护，即mp[i][j]表示以 i 为根的树上颜色 j 出现的次数，

然后对于每颗树，找出树上出现的次数最多的结点颜色相同的颜色， ans += (该树的总结点数) - 出现的次数最多的结点颜色相同的颜色的结点个数

复杂度 O(n)

#include 
#include 
#include 


#include 
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 8;

int father[maxn], _rank[maxn];
bool flag;
inline void DisjointSet(int n)
{
    for(int i = 0; i <= n; i++){
        father[i] = i;
    }
}

int _find(int v)
{
    return father[v] = father[v] == v ? v : _find(father[v]);
}

void _merge(int x, int y)
{
    int a = _find(x), b = _find(y);                //
    if(_rank[a] < _rank[b]){
        father[a] = b;
    }
    else{
        father[b] = a;
        if(_rank[a] == _rank[b]){
            _rank[a]++;
        }
    }
}

int val[maxn];
map<int, map<int, int> > mp;
map<int, int> ok;

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);


    int n, m, k, u, v;
    cin >> n >> m >> k;
    DisjointSet(n);
    for(int i = 1; i <= n; i++){ cin >> val[i];
    }
    for(int  i = 0; i < m; i++){ cin >> u >> v;
        ok[u]++;
        ok[v]++;
        if(_find(u) != _find(v)){
            //cout << "?"; _merge(_find(u), _find(v)); } } for(auto i = ok.begin(); i != ok.end(); i++){ mp[_find(i->first)][val[i->first]]++;
    }

    int ans = 0, sum = 0, maxv = 0;
    for(auto i = mp.begin(); i != mp.end(); i++){
        sum = 0; maxv = 0;
        for(auto j = (i->second).begin(); j != (i->second).end(); j++){
            //cout << j->second << " "; sum += j->second;
            maxv = max(maxv, j->second);
        }
        //cout << endl;
        ans += (sum - maxv);
    }

    cout << ans << endl;

    #ifdef LOCAL
    mp.clear();
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

------from ProLightsfx

Codeforces Round #376 (Div. 2) C. Socks 并查集+贪心、图论

相关推荐

HihoCoder – 1174 拓扑排序·一拓扑排序、BFS

AtCoder Petrozavodsk Contest 001 D – Forest 连通块+并查集+贪心

SGU – 465 Fire Station Building floyd+三分

Codeforces Round #385 (Div. 2) C. Hongcow Builds A Nation 并查集+贪心+组合学、图论、dfs

共有 0 条评论

公告

游戏服务器开发 最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发 最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

Codeforces Round #376 (Div. 2) C. Socks 并查集+贪心、图论

相关推荐

HihoCoder – 1174 拓扑排序·一 拓扑排序、BFS

AtCoder Petrozavodsk Contest 001 D – Forest 连通块+并查集+贪心

SGU – 465 Fire Station Building floyd+三分

Codeforces Round #385 (Div. 2) C. Hongcow Builds A Nation 并查集+贪心+组合学、图论、dfs

共有 0 条评论

公告

游戏服务器开发最新文章

1转行游戏开发第二年，开始修炼内功

2搜撤类游戏全服装备防复制方案

3从通用后台开发到游戏服务器开发...

公众号

推荐系统开发最新文章

1时序数据库与NB时序特征

2从零搭建NB特征平台

3NB特征分类标准

4浅谈NB推荐系统架构-ProLightsfx

5一次推荐系统线上事故的排查与修...

标签云

栏目分类

HihoCoder – 1174 拓扑排序·一拓扑排序、BFS