Posted in Math

POJ 2007

8/10/2017
Problem: http://poj.org/problem?id=2007
Solution: Sort all the points by cross product (of vectors). If v1 ^ v2 > 0,
then v1 can reach v2 rotating less than 180 degrees counter-clockwise.


#include<iostream>
#include<algorithm>
using namespace std;

struct node{
	double x, y;
	node(){}
	node(double xx, double yy):x(xx), y(yy){}
};

node n; 

bool cmp (node a, node b) {
	return (((a.x - n.x) * (b.y - n.y) - (a.y - n.y) * (b.x - n.x)) > 0);
}

int main() {
	double x, y;
	node p[105];
	int cnt = 0;
	cin >> n.x >> n.y;
	while (cin >> x >> y) {
		p[++cnt] = node(x, y);
	}
	sort(p + 1, p + cnt + 1, cmp);
	cout << "(0,0)" << endl;
	for(int i = 1; i <= cnt; i++) {
		cout << '(' << p[i].x << ',' << p[i].y << ")" << endl;
	} 
	return 0;
}

Posted in Kruskal

POJ 2349

8/8/2017
Problem: http://poj.org/problem?id=2349
Solution: The answer is just the length of the k-th largest edge in the MST.

#include<cstdio>
#include<iostream> 
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

struct point{
	int x, y;
	point(int xx, int yy):x(xx), y(yy){}
	point(){}
};

struct edge{
	int i, j;
	double w;
	edge(int ii, int jj, double ww):i(ii), j(jj), w(ww){}
	edge(){}
};

point p[5005];
edge e[251010];
int parent[5005];

double dist(int x1, int y1, int x2, int y2) {
	return sqrt((double)(x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

bool cmp(edge a, edge b) {
	return a.w < b.w;
}

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

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

int main() {
	int t;
	cin >> t;
	while (t--) {
		int s, n;
		cin >> s >> n;
		for (int i = 1; i <= n; i++) {
			parent[i] = i;
		} 
		for (int i = 1; i <= n; i++) {
			cin >> p[i].x >> p[i].y;
		} 
		int cnt = 0;
		for (int i = 1; i < n; i++) {
			for (int j = i + 1; j <= n; j++) {
				double tmp = dist(p[i].x, p[i].y, p[j].x, p[j].y);
				e[++cnt] = edge(i, j, tmp);
				e[++cnt] = edge(j, i, tmp);
			}
		}
		int node = 0;
		sort(e + 1, e + cnt + 1, cmp);
		for (int i = 1; i <= cnt; i++) {
			if (find(e[i].i) != find(e[i].j)) {
				merge(e[i].i, e[i].j);
				node++;
				if (node == n - s) {
					printf("%0.2f\n", e[i].w);
					break;
				}
			}
		}
	}
	return 0;
}
Posted in Kruskal

POJ 1258 Agri-Net

8/8/2017
Problem: http://poj.org/problem?id=1258
Solution: I used Kruskal but Prim is the same. Nothing noteworthy.


#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> parent;

struct Edge{
	int s, e, w;
	Edge(int ss, int ee, int ww):s(ss), e(ee), w(ww){}
};

vector<Edge> edge;

bool operator<(Edge a, Edge b) {
	return a.w < b.w;
}

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 (find(p1) != find(p2)) {
		parent[p2] = p1;
	}
}

int main() {
	int n;
	while (cin >> n) {
		parent.clear();
		edge.clear();
		for (int i = 0; i <= n; i++) {
			parent.push_back(i);
		}
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				int w;
				cin >> w;
				edge.push_back(Edge(i, j, w));
			}
		}
		sort(edge.begin(), edge.end());
		int node = 0;
		int len = 0;
		for (int i = 0; i < edge.size(); i++) {
			if (find(edge[i].s) != find(edge[i].e)) {
				merge(edge[i].s, edge[i].e);
				node++;
				len += edge[i].w;
			}
			if (node == n - 1) {
				break;
			}
		}
		cout << len << 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;
}