Pagini recente » Cod sursa (job #3344539) | Cod sursa (job #3310797) | Cod sursa (job #3351533) | Cod sursa (job #3310644) | Cod sursa (job #3348756)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
const int NMAX = 1e5 + 1;
vector <int> adj[NMAX];
int parent[NMAX];
int tin[NMAX], tmin[NMAX];
int t = 0;
stack <int> st;
vector <vector <int>> sol;
void add_biconex ( int nod, int nod_spate )
{
vector <int> comp;
while ( st.size() && st.top() != nod_spate )
{
comp.push_back(st.top());
st.pop();
}
comp.push_back(st.top());
st.pop();
comp.push_back(nod);
sol.push_back(comp);
}
void dfs ( int nod, int parent )
{
tin[nod] = tmin[nod] = ++ t;
st.push(nod);
for ( auto it : adj[nod] )
{
if ( it == parent )
continue;
if ( !tin[it] )
{
dfs ( it, nod );
tmin[nod] = min ( tmin[nod], tmin[it] );
if ( tmin[it] >= tin[nod] )
add_biconex( nod, it );
}
else tmin[nod] = min ( tmin[nod], tin[it] );
}
}
int main()
{
int n, m;
f >> n >> m;
for ( int i = 1; i <= m; i ++ )
{
int u, v;
f >> u >> v;
adj[v].push_back(u);
adj[u].push_back(v);
}
dfs ( 1, 0 );
g << sol.size() << '\n';
for ( auto v : sol )
{
for ( auto it : v )
g << it << " ";
g << '\n';
}
return 0;
}