P8436 【模板】边双连通分量
题目描述
对于一个nnn个节点mmm条无向边的图，请输出其边双连通分量的个数，并且输出每个边双连通分量。
输入格式
第一行，两个整数nnn和mmm。
接下来mmm行，每行两个整数u,vu, vu,v，表示一条无向边。
不保证图为简单图，图中可能有重边和自环。
输出格式
第一行一个整数xxx表示边双连通分量的个数。
接下来的xxx行，每行第一个数aaa表示该分量结点个数，然后aaa个数，描述一个边双连通分量。
你可以以任意顺序输出边双连通分量与边双连通分量内的结点。
输入输出样例 #1
输入 #1
5 8 1 3 2 4 4 3 1 2 4 5 5 1 2 4 1 1输出 #1
1 5 1 5 4 2 3输入输出样例 #2
输入 #2
5 3 1 2 2 3 1 3输出 #2
3 3 1 3 2 1 4 1 5输入输出样例 #3
输入 #3
6 5 1 3 2 4 1 2 4 6 2 3输出 #3
4 3 1 2 3 1 4 1 5 1 6输入输出样例 #4
输入 #4
7 8 1 3 2 4 3 5 2 5 6 4 2 5 6 3 2 7输出 #4
3 1 1 5 2 5 3 6 4 1 7说明/提示
样例四解释：
相同颜色的点为同一个连通分量。
数据范围：
对于100%100\%100%的数据，1≤n≤5×1051 \le n \le 5 \times10 ^51≤n≤5×105，1≤m≤2×1061 \le m \le 2 \times 10^61≤m≤2×106。
| subtask | nnn | mmm | 分值 |
|---|---|---|---|
| 111 | 1≤n≤1001 \le n \le 1001≤n≤100 | 1≤m≤5001 \le m \le 5001≤m≤500 | 252525 |
| 222 | 1≤n≤50001 \le n \le 50001≤n≤5000 | 1≤m≤5×1041 \le m \le 5 \times 10^41≤m≤5×104 | 252525 |
| 333 | 1≤n≤2×1051 \le n \le 2\times 10^51≤n≤2×105 | 1≤m≤5×1051 \le m \le 5\times 10^51≤m≤5×105 | 252525 |
| 444 | 1≤n≤5×1051 \le n \le 5 \times10 ^51≤n≤5×105 | 1≤m≤2×1061 \le m \le 2 \times 10^61≤m≤2×106 | 252525 |
数据更新
- 2022/7/142022/7/142022/7/14加强数据
- 2022/11/262022/11/262022/11/26新增101010组较小的数据（1≤n,m≤101\le n, m \le 101≤n,m≤10)，方便选手调试。
- 2022/12/312022/12/312022/12/31重组subtasksubtasksubtask，并加入若干组极端数据。
- 2023/1/12023/1/12023/1/1发现昨天新加入的数据数据出了问题，已修改。
本题不卡常，时间限制与空间限制均已开大，正确的解法均可通过。
惊喜：AC 后记得把鼠标放到测试点上看反馈信息，有惊喜哦。
C++实现
#include<bits/stdc++.h>usingnamespacestd;#defineMAXN500001intn,m,u,v,cnt;intdfn[MAXN],low[MAXN];vector<pair<int,int>>e[MAXN];vector<vector<int>>ans;stack<int>st;voidtarjan(intx,intlas){low[x]=dfn[x]=++cnt;st.push(x);for(autoi:e[x]){if(i.second==(las^1))continue;if(!dfn[i.first]){tarjan(i.first,i.second);low[x]=min(low[x],low[i.first]);}elselow[x]=min(low[x],dfn[i.first]);}if(dfn[x]==low[x]){vector<int>vec;vec.push_back(x);while(st.top()!=x){vec.push_back(st.top());st.pop();}st.pop();ans.push_back(vec);}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;for(inti(1);i<=m;++i){cin>>u>>v;e[u].push_back(make_pair(v,i<<1));e[v].push_back(make_pair(u,i<<1|1));}for(inti(1);i<=n;++i){if(!dfn[i])tarjan(i,0);}cout<<ans.size()<<'\n';for(autoi:ans){cout<<i.size()<<' ';for(autoj:i)cout<<j<<' ';cout<<'\n';}return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
