梧州建设厅官方网站,网站推广的四个阶段包括,百度搜索引擎网站,电子商务网站建设编码正题
题目链接:https://www.luogu.com.cn/problem/AT4518 题目大意
给出nnn个点mmm条边的一张简单无向联通图#xff0c;求能否把它分成三个可重复点的环。 1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105 解题思路
相当于你要去掉图上的两个环后依旧有欧拉回路
首先原本肯定得…正题
题目链接:https://www.luogu.com.cn/problem/AT4518 题目大意
给出nnn个点mmm条边的一张简单无向联通图求能否把它分成三个可重复点的环。 1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105 解题思路
相当于你要去掉图上的两个环后依旧有欧拉回路
首先原本肯定得有欧拉回路考虑怎么去掉这两个环。
如果图上有一个度数不小于666的点那么这个点就可以直接拉出三个环。
度数为222的点只能经过一遍显然不能分环。
那就只剩下度数为444的点了只有一个显然不行如果有三个或以上的度数为444的点那么直接拉出它们之间的路径就有三个环了
有两个的情况比较特殊其实是一定可以多拉出两个环的但是如果从某个度数为444的点出发的所有路径都必须经过另一个点那么拉出的这两个环会把图变得不连通所以需要特判一下这种情况。
时间复杂度O(nm)O(nm)O(nm) code
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
struct node{int to,next;
}a[N1];
int n,m,tot,ans,last,deg[N],ls[N];
bool v[N];
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(int x){if(v[x])return;v[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(deg[y]4){ans(ylast);lasty;}else dfs(y);}return;
}
int main()
{scanf(%d%d,n,m);for(int i1;im;i){int x,y;scanf(%d%d,x,y);addl(x,y);addl(y,x);deg[x];deg[y];}int cnt0,flag0;for(int i1;in;i)if(deg[i]1)return puts(No)0;else if(deg[i]6)flag1;else cnt(deg[i]4);if(flag||cnt2)return puts(Yes)0;if(cnt1)return puts(No)0;for(int i1;in;i)if(!v[i]deg[i]2)last0,dfs(i);if(ans)puts(Yes);else puts(No);return 0;
}
