Pagini recente » Cod sursa (job #1633359) | Cod sursa (job #2802023) | Cod sursa (job #998930) | Cod sursa (job #552184) | Cod sursa (job #1686425)
#include <fstream>
#include <vector>
#include <algorithm>
#define Pe pair <int, int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int MaxN = 100005;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
vector <Pe> Bicon;
vector <int> G[MaxN], partial_ans;
vector <vector <int>> Ans;
int depth[MaxN], highest[MaxN];
int n, m;
void BuildBicon(int end1, int end2) {
partial_ans.clear();
int n1 = Bicon.back().fi;
int n2 = Bicon.back().se;
Bicon.pop_back();
partial_ans.push_back(n1);
partial_ans.push_back(n2);
while(!Bicon.empty() and (n1 != end1 or n2 != end2)) {
n1 = Bicon.back().fi;
n2 = Bicon.back().se;
Bicon.pop_back();
partial_ans.push_back(n1);
partial_ans.push_back(n2);
}
sort(partial_ans.begin(), partial_ans.end());
partial_ans.erase(unique(partial_ans.begin(), partial_ans.end()), partial_ans.end());
Ans.push_back(partial_ans);
}
void Dfs(int node = 1, int level = 1, int father = 0) {
depth[node] = level;
highest[node] = level;
for(auto nxt: G[node]) {
if(father == nxt) {
continue;
}
if(!depth[nxt]) {
Bicon.push_back(mp(node, nxt));
Dfs(nxt, level + 1, node);
highest[node] = min(highest[node], highest[nxt]);
if(highest[nxt] >= level) {
BuildBicon(node, nxt);
}
}
else {
highest[node] = min(highest[node], depth[nxt]);
}
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
Dfs();
cout << Ans.size() << '\n';
for(auto ans: Ans) {
for(auto it: ans) {
cout << it << ' ';
}
cout << '\n';
}
return 0;
}