酒店网站模板,吴忠网页设计,做网站框架,关键词优化公司网站1 /*2 题目大意#xff1a;有两个不同的黑帮#xff0c;开始的时候不清楚每个人是属于哪个的#xff01;3 执行两个操作4 A a, b回答a, b两个人是否在同一帮派#xff0c;或者不确定5 D a, b表示a, b两个人不在同一个帮派6 7 思路#xff1a;利用并查集将相同帮… 1 /*2 题目大意有两个不同的黑帮开始的时候不清楚每个人是属于哪个的3 执行两个操作4 A a, b回答a, b两个人是否在同一帮派或者不确定5 D a, b表示a, b两个人不在同一个帮派6 7 思路利用并查集将相同帮派的人合并到一起8 a ,b 不在同一个城市那么 a, 和mark[b]就在同一个城市9 b 和 mark[a]就在同一个城市
10 */
11 #includeiostream
12 #includecstring
13 #includecstdio
14 #define M 100005
15 using namespace std;
16 int f[M];
17 int mark[M];//mark[i]表示 i 与 mark[i]不在同一个黑帮
18 int rank[M];//为不同的集合的父亲节点记录其孩子机节点个数在合并集合的时候将
19 int n, m; //rank 值小的集合连接到 rank 值大的集合上去 这样在路径压缩的时候省去不少时间
20
21 void init(){
22
23 memset(mark, 0, sizeof(int)*(n1));
24 memset(rank, 0, sizeof(int)*(n1));
25 for(int i1; in; i)
26 f[i]i;
27 }
28
29 int getFather(int x){
30 return xf[x] ? x : f[x]getFather(f[x]);
31 }
32
33 void Union(int a, int b){
34 int fagetFather(a), fbgetFather(b);
35 if(fa!fb){
36 if(rank[fa]rank[fb]){
37 f[fb]fa;
38 rank[fa]rank[fb]1;
39 }
40 else{
41 f[fa]fb;
42 rank[fb]rank[fa]1;
43 }
44 }
45 }
46
47 int main(){
48 int t;
49 char cmd[3];
50 scanf(%d, t);
51 while(t--){
52 scanf(%d%d, n, m);
53 init();
54 while(m--){
55 int u, v;
56 scanf(%s%d%d, cmd, u, v);
57 if(cmd[0]A){
58 int fugetFather(u), fvgetFather(v);
59 if(fufv)
60 printf(In the same gang.\n);
61 else if(fugetFather(mark[v]))
62 printf(In different gangs.\n);
63 else
64 printf(Not sure yet.\n);
65 }
66 else{
67 if(!mark[u] !mark[v]){
68 mark[u]v;
69 mark[v]u;
70 }
71 else if(!mark[u]){
72 mark[u]v;
73 Union(u, mark[v]);
74 }
75 else if(!mark[v]){
76 mark[v]u;
77 Union(v, mark[u]);
78 }
79 else {
80 Union(u, mark[v]);
81 Union(v, mark[u]);
82 }
83 }
84 }
85 }
86 return 0;
87 } 转载于:https://www.cnblogs.com/hujunzheng/p/3892571.html
