Pagini recente » Cod sursa (job #2417294) | Cod sursa (job #1054707) | Cod sursa (job #1093567) | Cod sursa (job #17405) | Cod sursa (job #1857032)
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
using VI = vector<int>;
vector<VI> G;
VI low, a;
int N;
vector<VI> C;
stack< pair<int, int> > st;
vector<bool> u;
void ReadGraph();
void DFS( int nod, int t, int nr );
void Add( int x, int y );
void Write();
int main()
{
ReadGraph();
DFS(1, 0, 0);
Write();
fin.close();
fout.close();
return 0;
}
void ReadGraph()
{
int M, x, y;
fin >> N >> M;
G = vector<VI>(N + 1);
a = VI(N + 1, -1);
low = VI(N + 1, N + 1);
u = vector<bool>(N + 1);
while ( M-- )
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void DFS( int nod, int t, int nr )
{
a[nod] = low[nod] = nr;
for ( const auto& v : G[nod] )
{
if ( v == t ) continue;
if ( a[v] == -1 ) // vecinul v inca nu a fost parcurs
{
st.push({nod, v});
DFS(v, nod, nr + 1);
low[nod] = min( low[nod], low[v] );
if ( a[nod] <= low[v] )
Add(nod, v);
}
else
{
low[nod] = min( low[nod], low[v] );
}
}
}
void Add( int x, int y )
{
int i, j;
VI n;
u = vector<bool>(N + 1, 0);
do
{
i = st.top().first, j = st.top().second;
if ( !u[i] )
{
n.push_back(i);
u[i] = true;
}
if ( !u[j] )
{
n.push_back(j);
u[j] = true;
}
st.pop();
}while ( !st.empty() && !( i == x && j == y ) );
C.push_back(n);
}
void Write()
{
fout << C.size() << '\n';
for ( const auto& x : C )
{
for ( const auto& y : x )
fout << y << ' ';
fout << '\n';
}
}