Pagini recente » Cod sursa (job #2507606) | Cod sursa (job #2932902) | Cod sursa (job #2765548) | Cod sursa (job #2243210) | Cod sursa (job #1970798)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
using VI = vector<int>;
vector<VI> G;
int N, M;
vector<VI> cb;
VI low, ind;
vector<bool> u;
int nr;
stack<pair<int, int>> st;
void Read();
void BiconnectedComponents();
void DFS( int nod, int t );
void Add( int x, int y );
void WriteComponents();
int main()
{
Read();
BiconnectedComponents();
WriteComponents();
fin.close();
fout.close();
return 0;
}
void Read()
{
int x, y;
fin >> N >> M;
G = vector<VI>(N + 1);
low = ind = VI(N + 1);
u = vector<bool>(N + 1);
while ( M-- )
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void BiconnectedComponents()
{
for ( int i = 1; i <= N; ++i )
if ( !ind[i] )
DFS(i, 0);
}
void DFS( int nod, int t )
{
ind[nod] = low[nod] = ++nr;
for ( const int& v : G[nod] )
{
if ( v == t )
continue;
if ( !ind[v] )
{
st.push({nod, v});
DFS(v, nod);
low[nod] = min( low[nod], low[v] );
if ( ind[nod] <= low[v] )
Add(nod, v);
}
else
low[nod] = min( low[nod], ind[v] );
}
}
void Add( int x, int y )
{
int a, b;
VI n;
do
{
a = st.top().first, b = st.top().second;
if ( !u[a] )
{
n.push_back(a);
u[a] = true;
}
if ( !u[b] )
{
n.push_back(b);
u[b] = true;
}
st.pop();
} while ( !st.empty() && !( a == x && b == y ) );
for ( const int& x : n )
u[x] = false;
cb.push_back(n);
}
void WriteComponents()
{
fout << cb.size() << '\n';
for ( const auto& x : cb )
{
for ( const int& y : x )
fout << y << ' ';
fout << '\n';
}
}