首页 > 代码库 > 51Nod 1515(并查集、set、离散化)
51Nod 1515(并查集、set、离散化)
//代码还是YY学姐帮改的,自己从来没有真正A过几道题,不是看题解就是有BUG找不出,多久了还是改变不了这样的现状,或许ACM就是这么筛选人的吧。从5.24到11.24,再到又一年的5.24,可感觉后者比前者过得快多了。多读了一年的大学,完全没有了时间概念,不知道现在到底是大几了,不知道现在到底处在什么位置,不知道毕业后到底从不从事IT这行,一切都是未知的。
题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1515
思路:数字范围为1e8,所以要先离散化,然后在每个连通块的祖先节点用一个set维护,两个联通块合并的时候对set作恰当处理。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 5; int father[N],r[N]; map <int,int> vis; set <int> s[N]; set <int> :: iterator it; struct node { int x,y,p; }q[N>>1]; int finds(int x) { if(father[x] != x) father[x] = finds(father[x]); return father[x]; } void connect(int a,int b) { if(r[a] > r[b]) { for(it = s[b].begin(); it != s[b].end(); it++) { int tmp = finds(*it); s[*it].erase(b); s[a].insert(tmp); s[tmp].insert(a); } father[b] = a; r[a]++; } else { for(it = s[a].begin(); it != s[a].end(); it++) { int tmp = finds(*it); s[*it].erase(a); s[b].insert(tmp); s[tmp].insert(b); } father[a] = b; r[b]++; } } int main() { int n,x,y,t = 1; scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d %d %d",&x,&y,&q[i].p); if(!vis[x]) { vis[x] = t; q[i].x = t++; } else q[i].x = vis[x]; if(!vis[y]) { vis[y] = t; q[i].y = t++; } else q[i].y = vis[y]; } for(int i = 1; i <= n; i++) { father[q[i].x] = q[i].x; father[q[i].y] = q[i].y; } for(int i = 1; i <= n; i++) { t = 0; x = finds(q[i].x); y = finds(q[i].y); if(q[i].p) { if(x == y) puts("YES"); else { if(s[x].count(y)) puts("NO"); else { puts("YES"); connect(x,y); } } } else { if(x == y) puts("NO"); else { puts("YES"); s[x].insert(y); s[y].insert(x); } } } return 0; }
51Nod 1515(并查集、set、离散化)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。