Pagini recente » Cod sursa (job #74074) | Cod sursa (job #720702) | Cod sursa (job #2816431) | Cod sursa (job #1786953) | Cod sursa (job #3040851)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5;
vector <int> edges[NMAX + 1];
int viz[NMAX + 1];
int found_time[NMAX + 1];
int min_time[NMAX + 1];
stack <int> st;
vector <int> biconexe[NMAX];
int t = 0, nrbic = 0;
void dfs( int node, int p ) {
viz[node] = true;
found_time[node] = min_time[node] = ++t;
st.push( node );
for ( auto vec : edges[node] ) {
if ( !viz[vec] ) {
dfs( vec, node );
min_time[node] = min( min_time[node], min_time[vec] );
if ( min_time[vec] >= found_time[node] ) {
while ( st.top() != vec ) {
biconexe[nrbic].push_back( st.top() );
st.pop();
}
biconexe[nrbic].push_back( vec );
st.pop();
biconexe[nrbic].push_back( node );
nrbic ++;
}
} else if ( vec != p && found_time[vec] < found_time[node] ) {
min_time[node] = min( min_time[node], found_time[vec] );
}
}
}
int main() {
ifstream fin( "biconex.in" );
ofstream fout( "biconex.out" );
int n, m, i, a, b;
fin >> n >> m;
for ( i = 0; i < m; i ++ ) {
fin >> a >> b;
edges[a].push_back( b );
edges[b].push_back( a );
}
for ( i = 1; i <= n; i ++ ) {
if ( !viz[i] ) {
dfs( i, 0 );
}
}
fout << nrbic << '\n';
for ( i = 0; i < nrbic; i ++ ) {
for ( auto it : biconexe[i] )
fout << it << ' ';
fout << '\n';
}
return 0;
}