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

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 )

Connecting to %s