HUD5438 Posted on 2017-01-20 | In Competitive Programming , HDU HUD 5438 PondsSolution SketchKey: Use DFS and yank nodes with $total\ degree = 1$ AC Code123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119#include <cstdio>#include <cstring>#include <queue>#include <vector>using namespace std;typedef long long ll;#define N 11111vector<int> g[N];int deg[N], val[N];queue<int> q;void clear(int n){ for (int i = 0; i <= n; i++) g[i].clear(); memset(deg, 0, sizeof(deg));}void add_edge(int u, int v){ g[u].push_back(v); g[v].push_back(u);}void dfs(int u){ if (deg[u] == 1) { deg[u] = 0; for (int i = 0; i < (int)g[u].size(); i++) { int v = g[u][i]; if (deg[v] > 0) { deg[v]--; dfs(v); } } } else { return; }}bool seen[N];int cnt = 0;ll total = 0;void dfs1(int u){ if (seen[u]) return; seen[u] = true; cnt++; total += val[u]; for (int i = 0; i < (int)g[u].size(); i++) { int v = g[u][i]; if (deg[v] > 0) { dfs1(v); } }}int main(){ int ncase; scanf("%d", &ncase); while (ncase--) { int n, m; scanf("%d %d", &n, &m); clear(n); for (int i = 0; i < n; i++) scanf("%d", &val[i]); for (int i = 0; i < m; i++) { int u, v; scanf("%d %d", &u, &v); u--; v--; add_edge(u, v); deg[u]++; deg[v]++; } ll sum = 0; for (int i = 0; i < n; i++) { if (deg[i] == 1) // starter q.push(i); } while (q.empty() == false) { int u = q.front(); q.pop(); dfs(u); } memset(seen, false, sizeof(seen)); for (int i = 0; i < n; i++) { if (deg[i] > 0 && seen[i] == false) { cnt = 0; total = 0; dfs1(i); if (cnt % 2 == 1 && cnt > 1) sum += total; } } printf("%lld\n", sum); } return 0;}