题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的数据