Posted in DSU

hdu 1272/ kuangbin 5-M(dsu)

10/17/2017
Problem: http://acm.split.hdu.edu.cn/showproblem.php?pid=1272
Solution: DSU. However, also need to check if all dots are connected. For that,
simply loop every dot that exists, and check if all their father are
the same.
Note: This problem would be much more easier if we consider the identity of a
tree, which is the number of dot is always one more than that of edges.
Link: https://prionanthaspace.wordpress.com/2017/10/18/hdu-1272-kuangbin-5-mgraph/


#include<iostream>
#include<string.h>
#include<cmath>
using namespace std;

int parent[100005] = {0};
int flag[100005] = {0};

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p1] = p2;
	}
}

int main() {
	int a, b;
	bool ans = true;
	int maxx = 0;
	int minn = 100005;
	for (int i = 1; i <= 100005; i++) {
		parent[i] = i;
	}	
	memset(flag, 0, sizeof(flag));
	while (cin >> a >> b) {
		if (a == -1 && b == -1) {
			return 0;
		} else if (!a && !b) {
			if (ans) {
				int tmp = find(minn);
				for (int i = minn + 1; i <= maxx; i++) {
					if (flag[i] && find(i) != tmp) {
						// cout << tmp << ' ' << find(i) << endl;
						ans = false;
						break;
					}
				}
			}		
			cout << (ans? "Yes" :"No") << endl;
			maxx = 0;
			minn = 100005;			
			ans = true;
			for (int i = 1; i <= 100005; i++) {
				parent[i] = i;
			}
			memset(flag, 0, sizeof(flag));
			continue;
		}
		minn = min(minn, min(a, b));
		maxx = max(maxx, max(a, b));
		flag[a] = 1;
		flag[b] = 1;
		if (find(a) != find(b)) {
			merge(a, b);
		} else {
			ans = false;
		}
	}
	return 0;
}

Posted in DSU

HDU 1213/ kuangbin 5-C

10/16/2017
Problem: http://acm.split.hdu.edu.cn/showproblem.php?pid=1213


#include<iostream>
#include<string.h>
using namespace std;

int parent[1005] = {0};
int cnt = 0;

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p1] = p2;
		cnt --;
	}
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		cnt =0;
		int n, m;
		cin >> n >> m;
		cnt = n;
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		}
		for (int i = 1; i <= m; i++) {
			int a, b;
			cin >> a >> b;
			if (find(a) != find(b)) {
				merge(a, b);
			}
		}
		cout << cnt << endl;
	}
	return 0;
} 

Posted in DSU

POJ 2236 Wireless Network

8/7/2017
Problem: http://poj.org/problem?id=2236
Solution: Still basic dsu..

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int x[1005];
int y[1005];
int parent[1005];
int ok[1005];
int d;

bool close(int a, int b) {
	if ((y[a] - y[b]) * (y[a] - y[b]) + (x[a] - x[b]) * 
						(x[a] - x[b]) <= d * d) {
		return true;					
	}
	return false;
}

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p1] = p2;
	}
}

int main() {
	int n;
	cin >> n >> d;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> y[i];
		parent[i] = i;
	} 
	string s;
	while (cin >> s) {
		if (s == "O") {
			int k;
			cin >> k;
			ok[k] = 1;
			for (int i = 1; i <= n; i++) {
				if (ok[i] && close(i, k) && find(i) != find(k)) {
					merge(i, k);
				}
			}
		} else if (s == "S") {
			int a, b;
			cin >> a >> b;
			if (find(a) == find(b)) {
				cout << "SUCCESS";
			} else {
				cout << "FAIL";
			}
			cout << endl;
		}
	}
	return 0;
}
Posted in DSU

POJ 2524 Ubiquitous Religions

8/7/2017
Problem: http://poj.org/problem?id=2524
Solution: Basic dsu, no explanation needed.

#include<iostream>
#include<cstring>
using namespace std;
int parent[50005];

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p1] = p2;
	}
}

int main() {
	int n, m;
	int c = 0;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) {
			return 0;
		}
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		}
		for (int i = 1; i <= m; i++) {
			int p, q;
			cin >> p >> q;
			if (find(p) != find(q)) {
				merge(p, q);
				n--;
			}
		}
		c++;
		cout << "Case " << c << ": ";
		cout << n << endl;
	}
	return 0;
}
Posted in DSU

PKU 30 Find it, Catch it

Problem: http://acmicpc.openjudge.cn/practice/030/


#include<iostream>
#include<cstdio>
#include<ctype.h>
using namespace std;
int parent[200005] = {0};

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p1] = p2;
	}
	return;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n, m;
		scanf("%d%d", &n, &m);
		if (n == 2 && m == 1) {
			cout << "In different gangs." << endl;
			char ch = 0;
			int a, b;
			while(!isalpha(ch)) {
				ch = getchar();
			}
			scanf("%d%d", &a, &b);
			continue;
		}
		for (int i = 1; i <= 2 * n; i++) {
			parent[i] = i;
		}
		for (int i = 1; i <= m; i++) {
			char ch = 0;
			int a, b;
			while(!isalpha(ch)) {
				ch = getchar();
			}
			scanf("%d%d", &a, &b);
			if (ch == 'D') {
				merge(a, b + n);
				merge(b, a + n);	
			} else if (ch == 'A') {
				int aa = find(a);
				int bb = find(b);
				if (find(a) == find(b + n)) {
					cout << "In different gangs." << endl; 
				} else if (aa != bb) {
					cout << "Not sure yet." << endl;
				} else {
					cout << "In the same gang." << endl;
				}
			}
		}
	} 
	return 0;
} 


Posted in DSU

PKU 29 Religion

Problem: http://acmicpc.openjudge.cn/practice/029/


#include<iostream>
#include<cstring>
using namespace std;
int parent[50005] = {0};

int find(int a) {
	if (parent[a] == a) {
		return a;
	} else {
		return parent[a] = find(parent[a]);
	}
}

void merge(int a, int b) {
	int p1 = find(a);
	int p2 = find(b);
	if (p1 != p2) {
		parent[p1] = p2;
	}
	return;
}

int main() {
	int n, m;
	int c = 0;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) {
			return 0;
		}
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		}
		c++;
		for (int i = 1; i <= m; i++) {
			int a, b;
			cin >> a >> b;
			if (find(a) != find(b)) {
				n--;
				merge(a, b);
			}
		}
		cout << "Case " << c << ": " << n << endl;
	}
	return 0;
}

Posted in DSU

PKU 28 A Bug’s Life

Problem: http://acmicpc.openjudge.cn/practice/028/


#include<iostream>
#include<cstdio>
using namespace std;
const int CON = 2000;
int parent[4005] = {0};

int find(int k) {
	if (parent[k] == k) {
		return k;
	} else {
		return find(parent[k]);
	}
}

void merge(int k1, int k2) {
	int p1 = find(k1);
	int p2 = find(k2);
	if (p1 == p2) {
		return;
	} else {
		parent[p1] = p2;
	}
}

int main() {
	ios::sync_with_stdio(false);
	int t;
	scanf("%d", &t);
	for (int p = 1; p <= t; p++) {
		bool b = false;
		for (int i = 1; i <= 4000; i++) {
			parent[i] = i;
		}
		int n, m;
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; i++) {
			int s1, s2;
			scanf("%d%d", &s1, &s2);
			merge(s1, s2 + CON);
			merge(s2, s1 + CON);
			if (find(s1) == find(s1 + CON) || find(s2) == find(s2 + CON)) {
				b = true;
			}
		}
		if (!b) {
			printf("Scenario #%d:\nNo suspicious bugs found!\n\n", p);
		} else {
			printf("Scenario #%d:\nSuspicious bugs found!\n\n", p);
		} 
	} 
	return 0;
}

Posted in DSU

PKU 27 Food Chain

Problem: http://acmicpc.openjudge.cn/practice/027/


#include<iostream>
#include<cstring> 
#include<cstdio>
using namespace std;
const int con = 50000;
int parent[150005] = {0};
int ans = 0;
int p, n;

int find(int k) {
	if (parent[k] == 0 || parent[k] == k) {
		parent[k] = k;
		return k;
	} else {
		parent[k] = find(parent[k]);
		return parent[k];
	}
}

void merge(int k1, int k2) {
	int p1 = find(k1);
	int p2 = find(k2);
	if (p1 == p2) {
		return;
	} else {
		parent[p1] = p2;
		return;
	}
}

bool judge1(int b, int c) {
	if (find(b + n) == find(c) || find(b + n * 2) == find(c)) {
		ans++;
		// cout << p << endl;
		return false;
	}
	return true;
}

bool judge2(int b, int c) {
	if (find(b) == find(c) || find(b + n * 2) == find(c)) {
		ans++;
		// cout << p << endl;
		return false;
	}
	return true;
}

int main() {
	ios::sync_with_stdio(false);
	int k;
	scanf("%d%d", &n, &k);
	memset(parent, 0, sizeof(parent));
	for (p = 1; p <= k; p++) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		if (b > n || c > n || (b == c && a == 2)) {
			ans++;
			// cout << p << endl;
		} else {
			if (a == 1) {
				if (judge1(b, c)) {
					merge(b, c);
					merge(b + n, c + n);
					merge(b + 2 * n, c + n * 2); 					
				}
			} else {
				if (judge2(b, c)) {
					merge(b + n, c);
					merge(b + n * 2, c + n);
					merge(b, c + n * 2);
				}
			}
		}
	}
	cout << ans;
	return 0;
} 

Posted in DSU

PKU 26 The Suspects

Problem: http://acmicpc.openjudge.cn/practice/026/


#include<iostream>
using namespace std;
const int con = 30005;
int parent[con];
int total[con];

int getParent(int a) {
	if (parent[a] != a) {
		parent[a] = getParent(parent[a]);
	}
	return parent[a];
}

void merge(int stu1, int stu2) {
	int p1 = getParent(stu1);
	int p2 = getParent(stu2);
	if (p1 == p2) {
		return;
	}
	total[p1] += total[p2];
	parent[p2] = p1;
}

int main() {
	int n, m;
	int stu1, stu2;
	while (cin >> n >> m) {
		if (n == 0 && m == 0) {
			return 0;
		}
		for (int i = 0; i <= n; i++) {
			parent[i] = i;
			total[i] = 1;
		} 
		for (int i = 1; i <= m; i++) {
			int k;
			cin >> k;
			cin >> stu1;
			for (int j = 1; j < k; j++) {
				cin >> stu2;
				merge(stu1, stu2);
			}
		}
		cout << total[getParent(0)] << endl;
	}
	return 0;
}

Posted in DSU

PKU 25 Cube Stacking

Problem: http://acmicpc.openjudge.cn/practice/025/


#include<iostream>
using namespace std;

int parent[30005] = {0};
int num[30005] = {0};
int dist[30005] = {0}; 

int find(int a) {
	if (parent[a] != a) {
		int father = parent[a];
		parent[a] = find(parent[a]);
		dist[a] += dist[father];
	}
	return parent[a];
}

int main() {
	int n;
	cin >> n;
	for (int i = 0; i<= 30005; i++) {
		parent[i] = i;
		num[i] = 1;
		dist[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		char ch;
		int a, b;
		cin >> ch;
		if (ch == 'M') {
			cin >> a >> b;
			int aa = find(a);
			int bb = find(b);			
			if (aa != bb) {
				parent[bb] = aa;
				dist[bb] = num[aa];
				num[aa] += num[bb];
			}
		} else {
			cin >> a;
			// cout << num[find] << ' ' << dist[a] << endl;
			cout << num[find(a)] - dist[a] - 1 << endl;
		}
	}
	return 0;
}