本文主要是介绍题76.天梯赛暑期结营测试-爱说假话的小A (25 分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
文章目录
- 题76.天梯赛暑期结营测试-爱说假话的小A (25 分)
- 一、题目
- 二、题解
题76.天梯赛暑期结营测试-爱说假话的小A (25 分)
一、题目
二、题解
本题采用并查集的操作去做,集合形成以后,检查输入时并非连通的两个的点(不是朋友)看它们是否为朋友关系就好(即是否为一个根)。需要注意三个点,第一,你真的是傻子哦,那个判断两点是否同根你当时怎么会想着是用parent是否相等来玩哦,肯定是要find_root去找根呀,然后再判断根是否相等。第二,这里我用了map来代替原来存每个点的父亲的数组,因为最后一个测试点会用到的下标太大了,根本开不了那么大的空间,直接就段错误了。。。第三,当你发现时间上还不够快蹦出个超时并且输入输出用的是cin和cout时,你不妨改用下scanf和printf,因为真的快好多。。。
#include <bits/stdc++.h>using namespace std;map<int,int> parent;int find_root(int v)
{if(parent[v]<0){return v;}else{//路径压缩return parent[v]=find_root(parent[v]);}
}void union_set(int v1,int v2)
{int root1=find_root(v1);int root2=find_root(v2);if(root1==root2){return;}//按秩归并if(parent[root1]<parent[root2]){parent[root1]+=parent[root2];parent[root2]=root1;}else{parent[root2]+=parent[root1];parent[root1]=root2;}return;
}struct Edge
{int v1,v2;
};int main()
{int t,n;scanf("%d",&t);for(int v=0;v<t;v++){parent.erase(parent.begin(),parent.end());//清空mapvector<Edge> G;cin>>n;for(int w=0;w<n;w++){int i,j,e;scanf("%d%d%d",&i,&j,&e);//一开始父亲都初始化为-1if(parent[i]==0){parent[i]=-1;}if(parent[j]==0){parent[j]=-1;}if(e==1){union_set(i,j);}else{Edge E;E.v1=i;E.v2=j;G.push_back(E);}}int flag=1;for(int w=0;w<G.size();w++){int root1,root2;root1=find_root(G[w].v1);root2=find_root(G[w].v2);if(root1==root2){flag=0;break;}}if(flag){printf("YES\n");}else{printf("NO\n");}}
}
补充:
map.erase(map.begin(),map.end())用于清空map的数据
这篇关于题76.天梯赛暑期结营测试-爱说假话的小A (25 分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!