Pagini recente » Cod sursa (job #3220098) | Cod sursa (job #1680781) | Cod sursa (job #527882) | Cod sursa (job #2318354) | Cod sursa (job #3197069)
#include <bits/stdc++.h>
#include <charconv>
#include <climits>
#include <fstream>
#include <string>
struct nod; std::vector<nod> noduri;
std::vector<int> articulatii;
std::stack<int> stack;
int componente = 0;
std::vector<char> output;
void push_output(int target) {
while(stack.top() != target) {
auto s = std::to_string(stack.top());
for(auto x: s) output.emplace_back(x);
output.emplace_back(' ');
stack.pop();
}
auto s = std::to_string(stack.top());
for(auto x: s) output.emplace_back(x);
output.emplace_back(' ');
output.emplace_back('\n');
stack.pop();
}
struct nod : std::vector<int> {
int depth;
int lowpoint;
bool visited;
bool articulatie;
nod() : depth(0), lowpoint(2e9), visited(false), articulatie(false) {}
};
void dfs(int nod_index, int depth, int parent) {
stack.push(nod_index);
auto& nod = noduri[nod_index];
nod.visited = true;
nod.depth = depth;
nod.lowpoint = depth;
for(auto i : nod) {
auto& v = noduri[i];
if(!v.visited) {
dfs(i, depth + 1, nod_index);
if(v.lowpoint >= nod.depth) {
nod.articulatie = true;
stack.push(nod_index);
push_output(i);
componente++;
}
nod.lowpoint = std::min(nod.lowpoint, v.lowpoint);
}
else if(i != parent)
nod.lowpoint = std::min(nod.lowpoint, v.depth);
}
//if((depth != 0 && nod.articulatie) || (depth == 0 && nod.size() > 1))
// articulatii.push_back(nod_index);
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int n, m; std::cin >> n >> m;
noduri.resize(n + 1);
while(m--) {
int a, b; std::cin >> a >> b;
noduri[a].push_back(b);
noduri[b].push_back(a);
}
dfs(1, 0, -1);
//for(auto x: articulatii) std::cout << x << ' ';
std::cout << componente << '\n';
for(auto x : output) std::cout << x;
return 0;
}