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