c/c++语言开发共享[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; }

一言

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