设为首页 加入收藏

TOP

[bzoj1116][POI2008][CLO]
2018-12-02 22:08:49 】 浏览:20
Tags:bzoj1116 POI2008 CLO

题目链接

思路

可以先考虑一棵树

如图,如果是一棵树我们肯定会想这样子做,但是现在根没有入度。所以现在需要再加入一条边使他变成基环树。

假如现在加入一条边\(3-2\),那就会出现一个3-1-2-3的环。然后以这个环上的点为根,就可以找到很多棵满足条件的树

可以发现,这样就解决了根没有入度的问题。

结论

每一个与环相连通的点都是合法的,只要判断是否存在不合法的点即可。

代码

/*
* @Author: wxyww
* @Date:   2018-12-02 20:15:02
* @Last Modified time: 2018-12-02 20:21:40
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
using namespace std;
typedef long long ll;
const int N = 100000 + 100,M = 200000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int col[N],fa[N];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main() {
    int n = read(),m = read();
    for(int i = 1;i <= n;++i) fa[i] = i;
    for(int i = 1;i <= m;++i) {
        int u = find(read()),v = find(read());
        if(u == v) {
            col[u] = 1;
            continue;
        }
        if(rand() & 1) swap(u,v);
        fa[u] = v;
        col[v] |= col[u];
    }
    for(int i = 1;i <= n;++i) {
        if(!col[find(i)]) {
            puts("NIE");
            return 0;
        }
    }
    puts("TAK");
    return 0;
}

一言

万丈红尘三杯酒,千秋大业一壶茶。 ——大智慧


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇洛谷P4165 [SCOI2007]组队(排序 .. 下一篇算法第三章实践报告

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }