Posted in ACM-ICPC, Graph theory

CF 977E Cyclic Components

Date: 5/8/2018
Problem: http://codeforces.com/problemset/problem/977/E
Solution: According to the definition, if several vertices are a cycle, all the vertices must have a degree of two. So, check only the vertices that has a degree of two, and see how many are circles can be constructed.


#include
#include
using namespace std;

int deg[200005] = {0};
bool vst[200005];
vector e[200005];
vector cycle;

void dfs(int i) {
	vst[i] = true;
	cycle.push_back(i);
	for (vector::iterator it = e[i].begin(); it != e[i].end(); ++it) {
		if (!vst[*it]) {
			dfs(*it);
		}
	}
}

int main() {
	int n, m;
	int ans = 0;
	cin >> n >> m;
	for (int i = 1; i > a >> b;
		deg[a]++;
		deg[b]++;
		e[a].push_back(b);
		e[b].push_back(a);
	}	
	for (int i = 1; i <= n; i++) {
		if (!vst[i]) {
			cycle.clear();
			vst[i] = true;
			dfs(i);
			bool b = true;
			for (vector::iterator it = cycle.begin(); it != cycle.end(); ++it) {
				if (deg[*it] != 2) {
					b = false;
					break;
				}
			}
			if (b) {
				ans++;
			}
		}
	}
	cout << ans;
	return 0;
}

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;
}