本文共 1614 字,大约阅读时间需要 5 分钟。
Write a program which reads relations in a SNS (Social Network Service), and judges that given pairs of users are reachable each other through the network.
In the first line, two integer nn and mm are given. nn is the number of users in the SNS and mm is the number of relations in the SNS. The users in the SNS are identified by IDs 0,1,...,n−10,1,...,n−1 .
In the following mm lines, the relations are given. Each relation is given by two integers ss and tt that represents ss and tt are friends (and reachable each other).
In the next line, the number of queries qq is given. In the following qq lines, qq queries are given respectively. Each query consists of two integers ss and tt separated by a space character.
For each query, print "yes" if tt is reachable from ss through the social network, "no" otherwise.
10 90 10 23 45 75 66 76 87 88 930 15 91 3
yesyesno
此题我一开始用的dfs, 然后超时, 发现需要在查询之前确定是否连通,于是乎想到了并查集。。 。做完发现并查集是真的快。 。dfs写了一遍, 但是不如并查集快。 。。
dfs:
#include#include #include #include #include using namespace std;const int maxn=100005;int n,m,q;int num;vector ve[maxn];int col[maxn];void init(){ num=0; memset (col,0,sizeof(col));}void dfs(int x,int nm){ col[x]=nm; for (int i=0;i
并查集:
#include#include #include #include #include using namespace std;const int maxn=100005;int n,m,q;int a[maxn];void init(){ for (int i=0;i
转载地址:http://uvaen.baihongyu.com/