/ Vijos / 讨论 / 家族 /

开始质疑STL的效率了...

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <set>
using namespace std;

void AddRelative(int self,int relative,bool flag=true)
{
if (people[self].count(relative)) //If "relative" has already been "self"'s relative
return ;
if (flag) //If function isn't called by itself
people[self].insert(relative);
for (set<int>::iterator it=people[relative].begin();it!=people[relative].end();++it)
{
if (self==*it)
continue;
AddRelative(self,*it);
}
AddRelative(relative,self,false);

}

int main()
{
int n,m,p;
cin>>n>>m>>p;
set<int>* people=new set<int>[n+1];
for (int i=1;i<=n;++i)
{
people[i].insert(i);
}
for (int i=0;i<m;++i)
{
int tmp1,tmp2;
cin>>tmp1>>tmp2;
AddRelative(tmp1,tmp2);
}
for (int i=0;i<p;++i)
{
int tmp1,tmp2;
cin>>tmp1>>tmp2;
cout<<(people[tmp1].count(tmp2) ? "Yes" : "No")<<endl;
}
delete people;
}

悲剧TLE了!

4 条评论

  • @ 2015-01-10 21:02:54

    用multimap实现并查集会快一些。

  • @ 2014-11-19 16:38:24

    前面加上std::ios::sync_with_stdio(0);

  • @ 2014-11-19 16:37:42

    前面加上std::ios::sync_with_stdio(0);

  • @ 2014-07-17 09:29:45

    流输入输出太慢了,scanf才是王道!!!!!

  • 1

信息

ID
1034
难度
4
分类
数据结构 | 并查集 点击显示
标签
(无)
递交数
9379
已通过
3848
通过率
41%
被复制
16
上传者