- 家族
- 2013-11-07 21:53:56 @
#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 条评论
-
lcdtyph LV 7 @ 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