Pagini recente » Cod sursa (job #2608) | Cod sursa (job #1936803) | Cod sursa (job #1705546) | Cod sursa (job #1353971) | Cod sursa (job #3237992)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ifstream fin( "biconex.in" );
ofstream fout( "biconex.out" );
const int DIM = 1e5 + 1;
vector<int> G[DIM];
int tin[DIM], timer;
int low[DIM];
vector<vector<int>> bcc;
vector<int> stk;
void insert_bcc( int u, int v ) {
vector<int> aux{u, v};
while ( stk.back() != v ) {
aux.push_back(stk.back());
stk.pop_back();
}
stk.pop_back();
bcc.push_back(aux);
}
void dfs( int u, int par = 0 ) {
low[u] = tin[u] = ++timer;
stk.push_back(u);
for ( auto v : G[u] ) {
if ( u == par ) continue;
if ( !tin[v] ) {
dfs(v, u);
low[u] = min(low[u], low[v]);
if ( low[v] >= tin[u] ) {
insert_bcc(u, v);
}
} else {
low[u] = min(low[u], tin[v]);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
fin.tie(0);
int n, m, u, v;
fin >> n >> m;
while ( m-- ) {
fin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1);
fout << bcc.size() << "\n";
for ( auto comp : bcc ) {
for ( auto u : comp ) {
fout << u << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}