当前位置: 首页 > news >正文

图论new

边双连通分量

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n, m, cnt, ans, dfn[N], low[N]; //dfn记录dfs序,low表示这个点除树边外能连到最浅 
vector<int> mp[N], mp2[N];
vector<int> s;
void shuru() {int u, v;cin >> n >> m;for(int i = 1; i <= m; i++){cin >> u >> v;mp[u].push_back(v);mp[v].push_back(u);}
}
void dfs(int u, int f){dfn[u] = low[u] = ++cnt; //记录dfs序并初始化low int cnt = 0; //用来判重边 s.push_back(u);for(auto v : mp[u]){if(v == f && !cnt){cnt = 1; continue;	}if(!dfn[v]) dfs(v, u);low[u] = min(low[u], low[v]);//更新low }if(low[u] == dfn[u]){//把在一个连通分量的点染成一个颜色++ans; //增加一个连通分量 while(1) {int x = s.back();s.pop_back();mp2[ans].push_back(x);if(x == u) break; }		}
}
void shuchu(){cout << ans << endl;for(int i = 1; i <= ans; i++){cout << mp2[i].size() << " ";for(auto x : mp2[i]) cout << x << " ";cout << endl;}
}
int main(){shuru();for(int i = 1; i <= n; i++){if(dfn[i]) continue;dfs(i,i);}shuchu();return 0;
}

割点

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4+5;
int n, m, cnt, tot, dfn[N], low[N], g[N];
vector<int> mp[N], v;
vector<int> s;
void shuru(){int u, v;cin >> n >> m;for(int i = 1; i <= m; i++){cin >> u >> v;if(u == v) continue; //特判自环 mp[u].push_back(v);mp[v].push_back(u);}
}
void dfs(int u, int f){dfn[u] = low[u] = ++cnt;for(auto v : mp[u]){if(v == f) continue;if(!dfn[v]){dfs(v, u);low[u] = min(low[u], low[v]);if(low[v] >= dfn[u]) g[u]++; //如果儿子的low比父亲还深,说明父亲是一个割点	}else low[u] = min(low[u], dfn[v]); //如果不是树边,就不会吃v==f的判断,用dfn判才不会影响判割点 }
}
int main(){shuru();for(int i = 1; i <= n; i++){if(dfn[i]) continue;dfs(i,i);g[i]--;//特判根节点 }for(int i = 1; i <= n; i++){if(g[i] > 0) v.push_back(i);}cout << v.size() << endl;for(auto x : v) cout << x << " ";return 0;
} 

点双连通分量

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int n, m, cnt, ans, dfn[N], low[N];
vector<int> mp[N], mp2[N];
vector<int> s;
void shuru(){int u, v;cin >> n >> m;for(int i = 1; i <= m; i++){cin >> u >> v;if(u == v) continue;mp[u].push_back(v);mp[v].push_back(u);}
}
void dfs(int u, int f){ //本质就是找割点 if(u == f && mp[u].empty()) { //一个点也是点双连通分量,要特判 ++ans;mp2[ans].push_back(u);}dfn[u] = low[u] = ++cnt;s.push_back(u);for(auto v : mp[u]){if(v == f) continue;if(!dfn[v]){dfs(v, u);low[u] = min(low[u], low[v]);if(low[v] >= dfn[u]){ //类似于边双连通,用栈维护 ++ans;while(1){int x = s.back(); s.pop_back();mp2[ans].push_back(x);if(x == v) break; }mp2[ans].push_back(u); //要把割点本身放进去 }}else low[u] = min(low[u], dfn[v]); //类似割点特判 }
}
void shuchu(){cout << ans << endl;for(int i = 1; i <= ans; i++){cout << mp2[i].size() << " ";for(auto x : mp2[i]) cout << x << " ";cout << endl;}
}
int main(){shuru();for(int i = 1; i <= n; i++){if(dfn[i]) continue;dfs(i,i);}shuchu();return 0;
}
http://www.hskmm.com/?act=detail&tid=24752

相关文章:

  • 2025夹丝玻璃厂家最新企业品牌推荐排行榜,艺术夹丝玻璃,淋浴房夹丝玻璃,极简门夹丝玻璃,金属夹丝玻璃公司推荐!
  • 斜率优化dp复习笔记
  • 掌握形式验证,护航芯片安全
  • 数位DP
  • 2025橡胶软接头厂家最新企业品牌推荐排行榜,法兰橡胶软接头,可曲挠,挠性,KXT,耐油,EPDM,耐腐蚀,三元乙丙橡胶软接头,橡胶柔性软接头公司推荐!
  • 整体二分笔记
  • 详细介绍:性能优化 - 案例篇:缓存_Guava#LoadingCache设计
  • 2025年X射线管厂家最新企业品牌推荐排行榜,工业用金属陶瓷,波长色散荧光分析,应力衍射分析,管板角焊缝,轮胎检测,辐照,固定阳极波纹陶瓷,测厚,食品检测 X 射线管公司推荐
  • AtCoder Beginner Contest 400
  • P14134 题解——随机化太帅了
  • 2025 年北京档案存放公司 升职猫档案服务平台:16 年老牌机构的合规服务与高效解决方案解析
  • 2025电容厂家最新品牌推荐排行榜白皮书,固态,高压,牛角,安规,CBB,超级,红宝石电解,螺栓,超级电容推荐这十家公司!
  • bug汇总
  • 2025石材加工厂家最新品牌推荐排行榜:大祥工艺,业务覆盖东北,辽宁盖州,专业浮雕雕刻高级技师
  • centos7升级降级内核 centos升级降级内核 centos升级内核 centos降级内核
  • Photoshop 在线网页版?是的,它来了!免费使用指南
  • 基于Python+Vue开发的母婴商城管理系统源码+运行步骤
  • 2025防火隔断品牌最新推荐排行榜:甲级防火玻璃隔断厂家深度解析,精选优质品牌助力采购决策!
  • 机器学习Day5-模型诊断 - 详解
  • 这些行业软件你用过哪个
  • 提供远程服务
  • 分享一些软件资讯
  • 2025美缝剂源头厂家最新推荐权威排行榜:深度解析五大品牌实力与选购指南
  • 2025数控铣床厂家最新企业品牌推荐排行榜, 双头数控铣床,双面数控铣床,龙门数控铣床,双侧数控铣床推荐这十家公司!
  • 2025最新推荐点胶机源头厂家权威排行榜:涵盖自动点胶机,果冻胶,无痕内衣,热熔胶类设备,助力企业精准挑选优质厂家
  • 前端开源JavaScrip库 - 详解
  • Probabilistic method小记
  • 数据生成方法初步调研
  • Elastic Stack 9.1.4 发布:重要安全更新与功能优化
  • 2025钛白粉源头厂家最新推荐排行榜:覆盖广东珠三角东莞华南深圳长三角地区的优质供应商解析