题目描述
历经千难万阻终于AC,坑在于p要开到200000,i也要遍历到200000
#include <iostream>
#include <cstring>
#include <unordered_map>
#include <vector>
using namespace std;
int n,t;
int p[200010];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
memset(p,0,sizeof p);
for(int i=1;i<=200010;i++)
{
p[i]=i;
}
unordered_map<int,int> map;
vector<pair<int,int>> err;
int num=0;
while(n--)
{
int a,b,op;
cin>>a>>b>>op;
//赋予a和b一个代号(离散化)
if(map[a]==0) map[a]=++num;
if(map[b]==0) map[b]=++num;
int fa,fb;
//先让相等的全都成立
if(op==1)
{
fa=find(map[a]);
fb=find(map[b]);
p[fb]=fa;
}
else
{
err.push_back({map[a],map[b]});
}
}
int flag=0;
for(int i=0;i<err.size();i++)
{
int a=err[i].first;
int b=err[i].second;
//cout<<a<<" "<<b<<endl;
if(find(a)==find(b))
{
flag=1;
cout<<"NO"<<endl;
break;
}
}
if(flag==0)
{
cout<<"YES"<<endl;
}
}
return 0;
}
二刷,总结一下这类问题的做法
先把正确的,即相等的加入一个集合,等待所有正确的加完之后,再判断错误的,若有矛盾则返回
有个注意点:在给a和b编号时,要注意先判断m[a]==0,没有再给,之前如果出现过就不用给了
#include <iostream>
#include <cstring>
#include <unordered_map>
#include <vector>
using namespace std;
const int N=200010;
int n,t;
int p[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
unordered_map<int,int> m;
vector<pair<int,int>> err;
int idx=0;
memset(p,0,sizeof p);
for(int i=1;i<=N;i++)
{
p[i]=i;
}
for(int i=1;i<=n;i++)
{
int a,b,e;
cin>>a>>b>>e;
if(m[a]==0) m[a]=++idx;
if(m[b]==0) m[b]=++idx;
if(e==1)
{
a=find(m[a]);
b=find(m[b]);
//cout<<a<<" "<<b<<endl;
if(a!=b)
{
p[a]=b;
}
}
else
{
err.push_back({m[a],m[b]});
}
}
int result=1;
for(int i=0;i<err.size();i++)
{
int a=err[i].first;
int b=err[i].second;
if(find(a)==find(b))
{
result=0;
break;
}
}
if(result==0) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
}
三刷,ac了,不难
先看数据范围,要离散化,使用unordered_map
另外有一点要注意,每个循环中初始化p[i]时,要从1-2*n。因为有n行关系,最多有2n个数出现
还有就是要注意要先把等于的关系全连上之后,最后再判断error关系,用一个vector保存所有的error对
#include <iostream>
#include <cstring>
#include <unordered_map>
#include <vector>
using namespace std;
const int N=200010;
typedef pair<int,int> pii;
int n,T;
int p[N];
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>T;
while(T--)
{
unordered_map<int,int> m;
cin>>n;
int cnt=0;
vector<pii> error;
memset(p,0,sizeof p);
for(int i=1;i<=2*n;i++)
{
p[i]=i;
}
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
if(!m[a]) m[a]=++cnt;
if(!m[b]) m[b]=++cnt;
if(c==1)
{
a=find(m[a]);
b=find(m[b]);
if(a!=b)
{
p[a]=b;
}
}
else
{
error.push_back({m[a],m[b]});
}
}
int flag=0;
for(int i=0;i<error.size();i++)
{
int a=error[i].first;
int b=error[i].second;
a=find(a);
b=find(b);
if(a==b)
{
flag=1;
break;
}
}
if(flag) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}