DFS HDOJ 5348 Ponds

题目传送门

题意：有一张无向图，度数小于2的点会被去掉，直到全都大于等于2，问连通块顶点数为奇数的权值和为多少

分析：首先DFS把度数小于2的vis掉，第二次DFS把属于同一个连通块的vis掉，检查是否为奇数个定点，是累加和。用sz[i]表示i点真实还连着的点的个数

代码：

/************************************************
* Author        :Running_Time
* Created Time  :2015/9/13 星期日 15:34:01
* File Name     :B.cpp
 ************************************************/

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e4 + 10;
const int E = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
vector<int> G[N];
int a[N], sz[N];
bool vis[N];
int n, m, cnt;
ll sum;

void init(void) {
    for (int i=1; i<=n; ++i)    G[i].clear ();
    memset (vis, false, sizeof (vis));
}

void DFS(int u)    {
    for (int i=0; i<G[u].size (); ++i)  {
        int v = G[u][i];
        if (vis[v]) continue;
        sz[v]--;
        if (sz[v] <= 1) {
            vis[v] = true;  DFS (v);
        }
    }
}

void DFS2(int u)    {
    sum += a[u];    cnt++;
    for (int i=0; i<G[u].size (); ++i)  {
        int v = G[u][i];
        if (vis[v]) continue;
        vis[v] = true;  DFS2 (v);
    }
}

int main(void)    {
    int T;  scanf ("%d", &T);
    while (T--) {
        scanf ("%d%d", &n, &m);
        init ();
        for (int i=1; i<=n; ++i)    scanf ("%d", &a[i]);
        for (int u, v, i=1; i<=m; ++i)  {
            scanf ("%d%d", &u, &v);
            G[u].push_back (v); G[v].push_back (u);
        }
        for (int i=1; i<=n; ++i)    sz[i] = G[i].size ();
        for (int i=1; i<=n; ++i)    {
            if (vis[i]) continue;
            if (sz[i] <= 1) {
                vis[i] = true;  DFS (i);
            }
        }
        ll ans = 0;
        for (int i=1; i<=n; ++i)    {
            if (vis[i]) continue;
            sum = 0;    cnt = 0;
            vis[i] = true;  DFS2 (i);
            if (cnt & 1)    ans += sum;
        }
        printf ("%I64d
", ans);
    }

    return 0;
}