Pagini recente » Cod sursa (job #2696343) | Cod sursa (job #1173173) | Cod sursa (job #2908732) | Cod sursa (job #2577171) | Cod sursa (job #2677388)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
//#define f cin
//#define g cout
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int NMAX = 100'001;
int N, M, low[NMAX], level[NMAX], biconnectedComponentsCnt;
vector < int > G[NMAX];
bitset < NMAX > V;
stack < int > Stack;
vector < int > biconnectedComponents[NMAX]; // pot fi maxim NMAX componente biconexe(cred)
void dfs(const int& node, const int& parent, const int& l) {
V[node] = 1;
level[node] = low[node] = l;
Stack.push(node);
for(const int& neighbor : G[node]) {
if(neighbor == parent) // nu vrem sa ne intoarcem de unde am venit
continue;
if(V[neighbor] == 1) { // muchia currenta este o muchie de intoarcere
low[node] = min(low[node], level[neighbor]); // aici am pus level[neighbor] pt ca muchia (node, neighbour)
// este muchie de intoarcere, caruia ii stim deja valoarea. BE AWARE: NU PUNE low[neighbor] pt ca o data ce
// muchia de intoarcere este folosita nu mai pot sa urc in "DFS TREE"
continue;
}
dfs(neighbor, node, l + 1);
low[node] = min(low[node], low[neighbor]);
if(low[neighbor] >= level[node]) { // daca "node" formeaza o noua componta biconexa
biconnectedComponentsCnt++;
int stackTopValue{};
do {
stackTopValue = Stack.top();
Stack.pop();
biconnectedComponents[biconnectedComponentsCnt].emplace_back(stackTopValue);
} while(stackTopValue != neighbor);
biconnectedComponents[biconnectedComponentsCnt].emplace_back(node);
}
}
}
int main() {
f >> N >> M;
while(M--) {
int u, v;
f >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1, 0, 1);
g << biconnectedComponentsCnt << "\n";
for(int i = 1;i <= biconnectedComponentsCnt;++i, g << '\n') {
for(const auto& it : biconnectedComponents[i])
g << it << ' ';
}
return 0;
}