POJ-1703 Find them, Catch them
并查集
数组建两倍于n的长度，分为两段，两段对应位置属于同一个人
D 时：
将第一段的p和第二段的q相互连接，同时第一段的q和第二段的p相互连接，代表 p、q 属于不同帮派。
A 时：
先判断在第一段内 p、q 是否相互连接，如果连接则一定属于同一帮派，因为 p、q 必定以某个敌对帮派的人物为桥梁才建立的连接。
如果不相连接则再判断 p、q + n 是否相连接，如果连接则一定属于不同帮派
如果上述都不满足则 p、q 关系不确定
Code
1/**
2 * author: Akvicor
3 * created: 2019-06-13 21-00-16
4**/
5
6#include <cstdio>
7#include <cstring>
8#include <iomanip>
9#include <ctime>
10#include <algorithm>
11#include <iostream>
12#include <string>
13#include <vector>
14#include <stack>
15#include <bitset>
16#include <complex>
17#include <cstdlib>
18#include <cmath>
19#include <set>
20#include <list>
21#include <deque>
22#include <map>
23#include <queue>
24
25using namespace std;
26
27#ifdef DEBUG
28string to_string(string s) {
29 return '"' + s + '"';
30}
31
32string to_string(const char* s) {
33 return to_string((string) s);
34}
35
36string to_string(bool b) {
37return (b ? "true" : "false");
38}
39
40template <typename A, typename B>
41string to_string(pair<A, B> p) {
42 return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
43}
44
45template <typename A>
46string to_string(A v) {
47 bool first = true;
48 string res = "{";
49 for (const auto &x : v) {
50 if (!first) {
51 res += ", ";
52 }
53 first = false;
54 res += to_string(x);
55 }
56 res += "}";
57 return res;
58}
59
60void debug_out() { cerr << endl; }
61
62template <typename Head, typename... Tail>
63void debug_out(Head H, Tail... T) {
64 cerr << " " << to_string(H);
65 debug_out(T...);
66}
67#endif
68
69#ifdef DEBUG
70#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
71#else
72#define debug(...) 17
73#endif
74
75#ifdef DEBUG
76#define FAST_IO 17
77#define cout cout << "-->"
78#else
79#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
80#define endl '\n'
81#endif
82
83#define LL long long
84#define ULL unsigned long long
85#define rep(i, n) for(int i = 0; i < (n); ++i)
86#define reep(i, n) for(int i = 0; i <= (n); ++i)
87#define lop(i, a, n) for(int i = a; i < (n); ++i)
88#define loop(i, a, n) for(int i = a; i <= (n); ++i)
89#define ALL(v) (v).begin(), (v).end()
90#define PB push_back
91#define VI vector<int>
92#define PII pair<int,int>
93#define FI first
94#define SE second
95#define SZ(x) ((int)(x).size())
96
97const double EPS = 1e-6;
98const double PI = acos(-1.0);
99const int INF = 0x3f3f3f3f;
100const LL LINF = 0x7f7f7f7f7f7f7f7f;
101const int MAXN = (int)1e6 + 10;
102const int MOD = (int)1e9 + 7;
103
104class UnionFind{
105 private:
106 int * parent;
107 int * rank;
108 int count;
109 public:
110 UnionFind(int n){
111 n *= 2;
112 n += 10;
113 parent = new int[n];
114 rank = new int[n];
115 this->count = n;
116 for(int i = 0; i < n; ++i){
117 parent[i] = i;
118 rank[i] = 1;
119 }
120 }
121 ~UnionFind(){
122 delete[] parent;
123 delete[] rank;
124 }
125
126 int find(int p){
127 while(p != parent[p]){
128 p = parent[p];
129 }
130 return p;
131 }
132
133 bool isConnected(int p, int q){
134 return find(p) == find(q);
135 }
136
137 void unionElements(int p, int q){
138 int pRoot = find(p);
139 int qRoot = find(q);
140
141 if(pRoot == qRoot) return;
142
143 if(rank[pRoot] < rank[qRoot]){
144 parent[pRoot] = qRoot;
145 }else if(rank[qRoot] < rank[pRoot]){
146 parent[qRoot] = pRoot;
147 }else{
148 parent[pRoot] = qRoot;
149 rank[qRoot] += 1;
150 }
151 }
152
153};
154
155int t, n, m, p, q;
156char c;
157
158int main(){
159 //FAST_IO;
160
161 //cin >> t;
162 scanf("%d\n", &t);
163 while(t--){
164 //cin >> n >> m;
165 scanf("%d %d\n", &n, &m);
166 UnionFind uf = UnionFind(n);
167 while(m--){
168 //cin >> c >> p >> q;
169 scanf("%c %d %d\n", &c, &p, &q);
170 if(c == 'D'){
171 uf.unionElements(p, n+q);
172 uf.unionElements(q, n+p);
173 }else{
174 if(uf.isConnected(p, q))
175 cout << "In the same gang." << endl;
176 else if(uf.isConnected(p, n+q))
177 cout << "In different gangs." << endl;
178 else cout << "Not sure yet." << endl;
179 }
180
181 }
182 }
183
184 return 0;
185}
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。