Posted in Graph theory

hdu 1272/ kuangbin 5-M(graph)

10/17/2017
Problem: http://acm.split.hdu.edu.cn/showproblem.php?pid=1272
Solution: Use the identity that for a tree, the number of nodes should be one
more than that of edges. Pay special attention to that there could be
zero node, but the answer should still be true.
Note: Another possible solution, using dsu, is posted here: https://prionanthaspace.wordpress.com/2017/10/18/hdu-1272-kuangbin-5-m/


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

int flag[100005] = {0};

int main() {
	int a, b;
	int cntn = 0, cnte = 0;
	while(cin >> a >> b) {
		if (a == -1 && b == -1) {
			return 0;
		} else if (!a && !b) {
			bool ans = (cntn == cnte + 1) || cntn == 0; 
			cout << (ans? "Yes": "No") << endl;
			memset(flag, 0, sizeof(flag));
			cntn = 0;
			cnte = 0;
			continue;
		}
		cnte ++;
		if (!flag[a]) {
			flag[a] = 1;
			cntn ++;
		}
		if (!flag[b]) {
			flag[b] = 1;
			cntn ++;
		}
	}
	return 0;
} 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s