## 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 = {0};
bool vst;
vector e;
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;
}

```

## 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 = {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;
}

```