Codeforces 893 Rumor 并查集/DFS

　　题目链接： http://codeforces.com/contest/893/problem/C

　　题目描述： 你可以收买每一个人，收买他之后相当于收买了他所有的朋友(双向的)，问最少多少钱可以收买到所有人。

　　解题思路： 典型的并查集， 自己看到这题就知道该怎么做， 无奈没有学习过图论， 就拿DFS做的， T掉了， 因为我很多重复的边都存进去了， 然后看别人的博客又学习到了新的姿势

　　代码： 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <list>
#include <iterator>
#include <cmath>
#include <cstring>
using namespace std;

const int maxn = 1e5+10;
int a[maxn];
const int INF = 0x3fffffff;
int n, d;

int main() {
    scanf("%d%d", &n, &d);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    int flag = 1;
    int top, bottom;
    int res = 0;
    top = bottom = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] == 0) {
            if(top < 0) {
                res++;
                top = d;            
            }
            bottom = max(0, bottom);
        }
        else {
            top += a[i];
               bottom += a[i];
            top = min(top, d);
            if(bottom > d) {
                flag = -1;
                break;
            }
        }
    }
    if(flag == 1) {
        printf("%d
", res);
    }
    else {
        printf("-1
");
    }
    return 0;
}

　　思考： 自己没有图论的经验是真的伤， 我一直在害怕图论不知道为什么， 所以打算学习图论了， ACM还是不想弃啊， 痛苦是痛苦， 但是对于自己算法能力和编程能力的提高却是真的， 为了走工程而放弃了自己坚持了一年多的ACM是不是太没有远见了？