BZOJ4668: 冷战(并查集)
2018-07-12 07:32:47来源:博客园 阅读 ()
Submit: 538 Solved: 269
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
0 1 4
1 2 5
0 2 4
0 3 4
1 3 1
0 7 0
0 6 1
0 1 6
1 2 6
Sample Output
3
5
HINT
Source
昨天zbq老司机用暴力启发式合并把codechef T6切了好强啊
感觉这东西也没啥玄学的吧,就是把小的往大的上面合并,时间复杂度为$O(nlogn)$
这题好像按高度合并也不错?
连的时候暴力连父亲就行,对答案没影响
#include<cstdio> #include<vector> #include<algorithm> #define Pair pair<int, int> #define MP(x, y) make_pair(x, y) using namespace std; const int MAXN = 500001, INF = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9'){if(c == '-')f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N, M; int fa[MAXN], h[MAXN], deep[MAXN], mx[MAXN], lastans = 0, siz[MAXN]; int find(int x) { if(x == fa[x]) return x; else { int f = find(fa[x]); deep[x] = deep[fa[x]] + 1; return f; } } void unionn(int x, int y, int tim) { int fx = find(x), fy = find(y); if(fx == fy) return; if(siz[fx] > siz[fy]) swap(fx, fy); fa[fx] = fy; siz[fy] += siz[fx]; mx[fx] = tim; } int query(int x, int y) { int fx = find(x), fy = find(y); if(fx != fy) return 0; int ans = 0; while(x != y) { if(deep[x] < deep[y]) swap(x, y); ans = max(ans, mx[x]); x = fa[x]; } return ans; } int main() { #ifdef WIN32 //freopen("a.in", "r", stdin); #endif N = read(); M = read(); for(int i = 1; i <= N; i++) fa[i] = i, siz[i] = 1; int id = 0; for(int i = 1; i <= M; i++) { int opt = read(), x = read() ^ lastans, y = read() ^ lastans; if(opt == 0) unionn(x, y, ++id); else printf("%d\n", lastans = query(x, y)); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 【图论】几个例题~ 2020-04-14
- 加边的无向图--并查集 2020-04-10
- [题记-并查集] 合根植物 - 蓝桥杯 2020-04-07
- 寒假集训第一天---并查集题解 2020-01-15
- 详解并查集 2019-11-02
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash