程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 1733(帶權並查集)

poj 1733(帶權並查集)

編輯:C++入門知識

poj 1733(帶權並查集)


題意:有n個結點,給出了q個操作,操作是a b string表示結點a到結點b的和是奇數或偶數,輸出x(前x個操作都是正確的)。
題解:帶權並查集經典題,因為結點可能有10,000,000,000個,所以需要離散化,不用的點就不考慮了。因為要a加到b,如果a==b無法找到各自的根節點並判斷是否要合並,所以其實是mp[a - 1]到mp[b]並入集合。另外需要注意結點是有順序的,父親結點要大於等於子節點,這樣判斷才不會出錯,所以合並時要考慮兩個根結點的大小有不同關系式。

#include 
#include
using namespace std;
const int N = 10005;
int pa[N], n, q, cnt, rel[N], l[N], r[N];
char str[N][10];
map mp;

int get_parent(int x) {
    if (pa[x] != x) {
        int px = get_parent(pa[x]);
        rel[x] = (rel[x] + rel[pa[x]]) % 2;
        pa[x] = px;
    }
    return pa[x];
}

int main() {
    while (scanf("%d", &n) == 1) {
        scanf("%d", &q);
        mp.clear();
        cnt = 1;
        for (int i = 1; i <= q; i++) {
            scanf("%d%d%s", &l[i], &r[i], str[i]);
            if (!mp[l[i] - 1])
                mp[l[i] - 1] = cnt++;
            if (!mp[r[i]])
                mp[r[i]] = cnt++;
        }
        for (int i = 0; i <= cnt; i++) {
            pa[i] = i;
            rel[i] = 0;
        }
        int res = -1;
        for (int i = 1; i <= q; i++) {
            int flag = str[i][0] == 'e' ? 0 : 1;
            int px = get_parent(mp[l[i] - 1]);
            int py = get_parent(mp[r[i]]);
            if (px != py) {
                if (px < py) {
                    pa[px] = py;
                    rel[px] = (flag + rel[mp[r[i]]] - rel[mp[l[i] - 1]] + 2) % 2;
                }
                else {
                    pa[py] = px;
                    rel[py] = (rel[mp[l[i] - 1]] - flag - rel[mp[r[i]]] + 4) % 2;
                }
            }
            else {
                if ((rel[mp[l[i] - 1]] - rel[mp[r[i]]] + 2) % 2 != flag) {
                    res = i - 1;
                    break;
                }
            }
        }
        if (res == -1)
            res = q;
        printf("%d\n", res);
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved