Pagini recente » Cod sursa (job #3224237) | Cod sursa (job #538906) | Cod sursa (job #692313) | Cod sursa (job #1146191) | Cod sursa (job #1582936)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int MAX_N = 100000;
int n, m, biconCount;
vector < int > A[1 + MAX_N];
int H[1 + MAX_N];
int lowLink[1 + MAX_N];
stack < pair < int, int > > S;
vector < int > bicon[1 + MAX_N];
void dfs(int u, int parent) {
lowLink[u] = H[u];
for(auto v : A[u]) {
if(v != parent) {
if(H[v]) {
lowLink[u] = min(lowLink[u], H[v]);
}
else {
H[v] = H[u] + 1;
S.push(make_pair(u, v));
dfs(v, u);
if(lowLink[v] >= H[u]) {
biconCount++;
while(!S.empty() && (S.top().first != u || S.top().second != v)) {
bicon[biconCount].push_back(S.top().second);
//out << S.top().first << " <-> " << S.top().second << '\n';
S.pop();
}
//out << u << " <-> " << v << '\n';
bicon[biconCount].push_back(u);
bicon[biconCount].push_back(v);
S.pop();
}
lowLink[u] = min(lowLink[u], lowLink[v]);
}
}
}
}
void getBicon() {
for(int i = 1; i <= n; i++) {
if(H[i] == 0) {
H[i] = 1;
dfs(i, 0);
}
}
}
int main() {
int i, u, v;
in >> n >> m;
for(i = 1; i <= m; i++) {
in >> u >> v;
A[u].push_back(v);
A[v].push_back(u);
}
getBicon();
out << biconCount << '\n';
for(i = 1; i <= biconCount; i++) {
for(auto j : bicon[i]) {
out << j << ' ';
}
out << '\n';
}
return 0;
}