HDU 1325 – Is It A Tree? [并查集]

vjudge题目链接

题意:给定一个图的n条有向边,判断是否为树

满足树的条件:

  1. 只有一个根结点
  2. 不能成环
  3. 每个节点的入度<=1
  4. 任意两个节点有且仅有一条通路,即不能成为森林

用并查集判断即可。注意程序结束的条件是输入两个小于0的整数,而不是两个-1.

 

#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 102400;
vector<pair<int, int> > v;
int par[maxn], vis[maxn];
void Init(){
    for(int i = 0; i < maxn; ++i)
        par[i] = i;
    memset(vis, false, sizeof(vis));
    v.clear();
}
int Find(int x){return x==par[x] ? x : par[x]=Find(par[x]); }


int main(){
    int x, y, kase = 0; Init();
    while(~scanf("%d%d", &x, &y)){
        if(x < 0) return 0;
        if(x == 0  && y == 0) {
            bool ok = true;
            for(int i = 0; i != v.size(); ++i){
                int a = Find(v[i].first), b = Find(v[i].second);
                if(a == b || b != v[i].second) {
                    ok = false;
                    break;
                }
                else par[b] = a;
            }
            if(ok) {
                int cnt = 0;
                for(int i = 0; i < maxn; ++i)
                    if(vis[i] && Find(i)==i)
                        ++cnt;
                if(cnt > 1) ok = false;
            }
            if(ok) printf("Case %d is a tree.\n", ++kase);
            else printf("Case %d is not a tree.\n", ++kase);
            Init();
        }
        else v.push_back(make_pair(x, y)), vis[x]=vis[y]=true;
    }
    return 0;
}

欢迎留言