ProLightsfx的技术成长

Hi!请登陆

AtCoder – 2159 Connectivity 并查集+二分、快速的求出2个集合的交集

ProLightsfx 2017-1-17 104 1/17

A - 連結 / Connectivity 并查集+二分、快速的求出2个集合的交集

 Source

AtCoder - 2159

https://vjudge.net/contest/147744#problem/A

 

My Solution

题意：分别有一个road网络和一个railway网络，求每个点在2个网络中都连通的点的个数。

 

并查集+二分

先用并查集维护出2个网络的连通关系，然后把这些树转移到 map<int, vector> mp里，

//bitset 超时

每次对于每个i，如果没有计算过ans，则比较mp1[_find(i)]和mp2[_find2(2)]这2个vector里相同的元素的个数，并且这些相同的数它们的ans都是一样的，

比如把这些相同元素维护到一个map<int, bool> m里，则所有的m.first的ans都是m.size,下次i遍历到这些点时可以直接continue。

直接比较2个vector时会超时，所有采用的优化方法是 在得到vector后直接对每一个vector进行排序，然后用a、b2个指针分别指向2个vector中的当前元素，不满足时用二分的方法找到指针需要指向的下一个元素的位置。

复杂度 O(nlogn)

 

#include 
#include 
#include 
#include 

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

//有时可能需要 并查集+离散化

//并查集可以直接写成1个类，然后2个并查集建2个对象就可以，这里就直接朴素写法的并查集了 Y ^_^ Y
int father[maxn], _rank[maxn];
inline void DisjointSet(int n)
{
    for(int i = 0; i <= n; i++){
        father[i] = i;
        _rank[i] = 0;
    }
}

inline int _find(int v)
{
    return father[v] = father[v] == v ? v : _find(father[v]);
    //同时压缩路径，有时不能压缩路径，有时必须压缩路径，看具体情况
}

inline 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 father1[maxn], _rank1[maxn];
inline void DisjointSet1(int n)
{
    for(int i = 0; i <= n; i++){
        father1[i] = i;
        _rank1[i] = 0;
    }
}

inline int _find1(int v)
{
    return father1[v] = father1[v] == v ? v : _find1(father1[v]);
    //同时压缩路径，有时不能压缩路径，有时必须压缩路径，看具体情况
}

inline void _merge1(int x, int y)
{
    int a = _find1(x), b = _find1(y);                //
    if(_rank1[a] < _rank1[b]){
        father1[a] = b;
    }
    else{
        father1[b] = a;
        if(_rank1[a] == _rank1[b]){
            _rank1[a]++;
        }
    }
}


map<int, vector> mp1, mp2;
map<int, int> cnt;
int ans[maxn];

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


    int n, p, q, u, v;
    cin >> n >> p >> q;
    DisjointSet(n), DisjointSet1(n);
    while(p--){
        cin >> u >> v;
        if(_find(u) != _find(v)) _merge(_find(u), _find(v));
    }

    while(q--){
        cin >> u >> v;
        if(_find1(u) != _find1(v)) _merge1(_find1(u), _find1(v));
    }

    for(int i = 1; i <= n; i++){
        mp1[_find(i)].push_back(i);
    }
    for(int i = 1; i <= n; i++){ mp2[_find1(i)].push_back(i); } for(auto i = mp1.begin(); i != mp1.end(); i++){ sort((i->second).begin(), (i->second).end());
    }
    for(auto i = mp2.begin(); i != mp2.end(); i++){
        sort((i->second).begin(), (i->second).end());
    }

    //cout << "?"<<endl;

    int i, j, a, b, pa, pb, sza, szb, l, r, mid;
    for(i = 1; i <= n; i++){
        if(ans[i] != 0) continue;
        pa = _find(i); pb = _find1(i);
        sza = mp1[pa].size(), szb = mp2[pb].size();
        cnt.clear();
        a = 0, b = 0;
        while(a < sza && b < szb){ if(mp1[pa][a] == mp2[pb][b]){ cnt[mp1[_find(i)][a]]++; a++; b++; } else if(mp1[pa][a] > mp2[pb][b]){
                if(b + 1== szb){
                    break;
                }
                else if(mp1[pa][a] > mp2[pb][szb - 1]){
                    break;
                }
                else{
                    l = b, r = szb;
                    b = szb - 1;
                    while(l + 1 < r){ mid = (l + r) >> 1;
                        if(mp1[pa][a] <= mp2[pb][mid]){
                            r = mid;
                            b = min(b, mid);
                        }
                        else l = mid;
                    }

                }
            }
            else{
                if(a + 1 == sza){
                    break;
                }
                else if(mp1[pa][sza - 1] < mp2[pb][b]){
                    break;
                }
                else{
                    l = a, r = sza;
                    a = sza - 1;
                    while(l + 1 < r){ mid = (l + r) >> 1;
                        if(mp1[pa][mid] >= mp2[pb][b]){
                            r = mid;
                            a = min(a, mid);
                        }
                        else l = mid;
                    }
                }
            }
        }
        sza = cnt.size();
        for(auto k = cnt.begin(); k != cnt.end(); k++){
            ans[k->first] = sza;
        }
    }

    for(i = 1; i <= n; i++){
        if(i == 1) cout << ans[i];
        else cout << " " << ans[i];
    }


    cout << endl;

    #ifdef LOCAL
    memset(ans, 0, sizeof ans);
    mp1.clear();
    mp2.clear();
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

 


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

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx

- THE END -
Tag：

ProLightsfx

11月15日19:53

最后修改：2024年11月15日
0

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

相关推荐

UVALive – 4294 Shuffle 映射+取反+最大区间覆盖

UVALive – 4294 Shuffle 映射+取反+最大区间覆盖

2017-1-21 93℃
UESTC 1705 咸鱼钟大爷 随机化+哈希

UESTC 1705 咸鱼钟大爷 随机化+哈希

2017-7-18 129℃
OpenJ_POJ C16D Extracurricular Sports 找规律、大整数类

OpenJ_POJ C16D Extracurricular Sports 找规律、大整数类

2017-5-4 109℃
AIM Tech Round 3 (Div. 2) B. Checkpoints 排序、讨论

AIM Tech Round 3 (Div. 2) B. Checkpoints 排序、讨论

2016-8-26 100℃

共有 0 条评论

emoji表情
😀 😃 😄 😁 😆 😅 😂 🤣 ☺️ 😇 🙂 🙃 😉 😌 😍 😘 😗 😙 😚 😋 😜 😝 😛 🤑 🤓 😎 🤡 🤠 😏 😒 🤗 😞 😔 😟 😕 🙁 ☹️ 😣 😖 😫 😩 😤 😠 😡 😶 😐 😑 😯 😦 😧 😮 😲 😵 😳 😱 😨 😰 😢 😥 🤤 😭 😓 😪 😴 🙄 🤔 🤥 😬 🤐 🤢 🤧 😷 🤒 🤕 😣 😖 😫 😩 😤 😠 😡 😶 😐 😑 😯 😦 😧 😮 😲 😵 😳 😱 😨 😰 😢 😥 🤤 😭 😓 😪 😴 🙄 🤔 🤥 😬 🤐 🤢 🤧 😷 🤒 🤕 😈 👿 👹 👺 💩 👻 💀 ☠️ 👽 👾 🤖 🎃 😺 😸 😹 😻 😼 😽 🙀 😿 😾 👐🏻 🙌🏻 👏🏻 🙏🏻 🤝 👍 👎🏻 👊🏻 ✊🏻 🤛🏻 🤜🏻 🤞🏻 ✌🏻 🤘🏻 👌 👈🏻 👉🏻 👆🏻 👇🏻 ☝🏻 ✋🏻 🤚🏻 🖐🏻 🖖🏻 👋🏻 🤙🏻 💪🏻 🖕🏻 ✍🏻 🤳🏻 💅🏻 💍 💄 💋 👄 👅 👂🏻 👃🏻 👣 👀 👤 👥 👶🏻 👦🏻 👧🏻 👨🏻 👩🏻 👱🏻‍♀️ 👱🏻 👴🏻 👵🏻 👲🏻 👳🏻‍♀️ 👳🏻 👮🏻‍♀️ 👮🏻 👷🏻‍♀️ 👷🏻 💂🏻‍♀️ 💂🏻 🕵🏻‍♀️ 🕵🏻 👩🏻‍⚕️ 👨🏻‍⚕️ 👩🏻‍🌾 👩🏻‍🍳 👨🏻‍🍳 👩🏻‍🎓

公告

ProLightsfx简介：Pro是program（编程的意思），Lights是光线，fx和fxjh是名字缩写。
联系方式：prolightsfx@126.com 或prolightsadmin@163.com


1.笔者小时候语文不大好[狗头]，要是哪句话写的不通顺，欢迎评论留言。
2.如果笔者的文章有冒犯到你，还请邮件通知整改。

公众号

WordPress的邮件订阅功能和评论功能感觉不大好用，
如果对笔者的文章感兴趣的话，欢迎关注公众号，一起学习成长。

ProLighsfx的公众号

关于 | 隐私政策| sitemap| 友情链接

文章数量: 317| 博客总访问量(包括之前csdn的访问量): 583089| 本站新访问量: 57058

Copyright © ProLightsfx的技术成长 Powered WordPress Theme Qzdy