首页 > 代码库 > 51nod 1515 明辨是非 [并查集+set]
51nod 1515 明辨是非 [并查集+set]
今天cb巨巨突然拿题来问，感觉惊讶又开心，希望他早日康复！！坚持学acm！加油！
这题一看感觉我写不出来orz，
就晚睡一点也要把WA的代码改AC！！
好困啊，直接贴了睡觉.zZ
题目链接：51nod 1515 明辨是非 [并查集]
1515 明辨是非
题目来源： 原创
基准时间限制：1 秒 空间限制：131072 KB 分值: 160 难度：6级算法题
给n组操作，每组操作形式为x y p。
当p为1时，如果第x变量和第y个变量可以相等，则输出YES，并限制他们相等；否则输出NO，并忽略此次操作。
当p为0时，如果第x变量和第y个变量可以不相等，则输出YES，并限制他们不相等 ；否则输出NO，并忽略此次操作。
Input
输入一个数n表示操作的次数(n<=1*10^5)接下来n行每行三个数x,y,p（x,y<=1*10^8,p=0 or 1）
Output
对于n行操作，分别输出n行YES或者NO
Input示例
31 2 11 3 12 3 0
Output示例
YESYESNO
#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>#include <string>#include <cmath>#include <queue>#include <set>#include <map>#include <limits.h>#define CLR(a,b) memset((a),(b),sizeof((a)))using namespace std;typedef long long ll;const int N = 1e5+5;int fa[N], r[N];map <int, int> vis;set <int> s[N];set <int> :: iterator it;struct node{ int x, y, p;}q[N];int fin(int x) { if(x != fa[x]) fa[x] = fin(fa[x]); return fa[x];}void uni(int a, int b) { if(r[a] > r[b]) { for(it = s[b].begin(); it != s[b].end(); it++) { // s[a].insert(*it); int x = fin(*it); s[*it].erase(b); s[a].insert(x); s[x].insert(a); } fa[b] = a; r[a]++; } else { for(it = s[a].begin(); it != s[a].end(); it++) { //s[b].insert(*it); int x = fin(*it); s[*it].erase(a); s[b].insert(x); s[x].insert(b); } fa[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) { fa[q[i].x] = q[i].x; fa[q[i].y] = q[i].y; } for(int i = 1; i <= n; ++i) { t = 0; x = fin(q[i].x); y = fin(q[i].y); if(q[i].p) { if(x == y) puts("YES"); else { /*for(it = s[x].begin(); it != s[x].end(); it++) { if(s[y].count(*it)) { t = 1; break; } } for(it = s[y].begin(); it != s[y].end(); it++) { if(s[x].count(*it)) { t = 1; break; } } if(t) puts("NO");*/ if(s[x].count(y) || s[y].count(x)) puts("NO"); else { puts("YES"); uni(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个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。