【hihocoder】欧拉路径 并查集判连通
2024-08-26 21:58:54
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue> using namespace std;
int n,m;
const int maxn=1e4+;
const int maxm=5e4+;
int degree[maxn];
int fa[maxn];
struct edge{
int to;
int nxt;
}e[*maxm];
int head[maxn];
int tot;
void init(){
memset(head,-,sizeof(head));
tot=;
memset(degree,,sizeof(degree));
}
void add(int u,int v){
e[tot].to=v;
e[tot].nxt=head[u];
head[u]=tot++;
}
int getfa(int u){
if(fa[u]==u) return u;
return fa[u]=getfa(fa[u]);
}
void merge(int u,int v){
int fu=getfa(u);
int fv=getfa(v);
if(fu!=fv){
fa[u]=fa[v];
}
} bool judge(){
for(int i=;i<=n;i++){
fa[i]=i;
}
for(int u=;u<=n;u++){
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
merge(u,v);
}
}
int cnt=;
for(int i=;i<=n;i++){
if(fa[i]==i) cnt++;
}
if(cnt==) return true;
return false;
}
int main(){
while(~scanf("%d%d",&n,&m)){
init();
int u,v;
for(int i=;i<=m;i++){
scanf("%d%d",&u,&v);
degree[u]++;
degree[v]++;
add(u,v);
add(v,u);
}
bool connected=judge();
if(!connected){
printf("Part\n");
continue;
}
int cnt=;
for(int i=;i<=n;i++){
if(degree[i]%) cnt++;
}
if(cnt==||cnt==) printf("Full\n");
else printf("Part\n");
}
return ;
}
最新文章
- ntp
- 苹果下如果安装nginx,给nginx安装markdown第三方插件
- java多线程总结
- Java中的4种代码块
- PHP获取汉字的转化为拼音字母实现程序
- 《A Tour of PostgreSQL Internals》学习笔记——进程间通信
- Mysql在windows下的免安装配置步骤和重新安装的步骤
- C++ 遇见的一些函数
- bzoj1443
- sql server在使用xp_cmdshell
- linux如何关闭selinux?
- vue-router实例
- SpringMVC中的拦截器
- P1378 油滴扩展 dfs回溯法
- jquery简介未完成
- C# Http文件上传下载
- Python Appium 元素定位方法简单介绍
- springboot集成AOP管理日志
- C#:将数据网格内的数据导出到Excel
- linux 配置svn服务器+使用+注意事项