题目链接
思路
可以先考虑一棵树
如图,如果是一棵树我们肯定会想这样子做,但是现在根没有入度。所以现在需要再加入一条边使他变成基环树。
假如现在加入一条边(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; }
一言
万丈红尘三杯酒,千秋大业一壶茶。 ——大智慧
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606121.html