Pagini recente » Cod sursa (job #431345) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #657079) | Cod sursa (job #1536044)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, nr, root;
vector<vector<int>> G, Cb;
vector<int> niv, L, t, c;
vector<bool> p_art;
stack<pair<int, int>> st;
pair<int, int> p;
void Read();
void Tarjan(int x, int nv);
int main()
{
Read();
root = 1;
Tarjan(root, 1);
int x, y;
fout << Cb.size() << '\n';
for ( auto g : Cb )
{
for ( auto z : g )
fout << z << ' ';
fout << '\n';
}
return 0;
}
void Read()
{
fin >> n >> m;
int x, y;
G = vector<vector<int>>(n + 1);
niv = vector<int>(n + 1);
L = vector<int>(n + 1);
p_art = vector<bool>(n + 1);
t = vector<int>(n + 1);
for ( int i = 1; i <= m; i++)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void Tarjan(int x, int nv)
{
if ( nv == 2 )
nr++;
L[x] = niv[x] = nv;
for ( auto y : G[x] )
{
if ( !niv[y] )
{
t[y] = x;
st.push({x, y});
Tarjan(y, nv + 1);
L[x] = min(L[y], L[x]);
}
else
if ( t[x] != y )
L[x] = min(L[x], niv[y]);
}
if ( t[x] == root && nr > 1)
{
p_art[t[x]] = 1;
do
{
p = st.top();
st.pop();
c.push_back(p.second);
}while( (p.first != t[x] && p.second != x) && !st.empty());
c.push_back(p.first);
Cb.push_back(c);
c.clear();
}
if ( L[x] >= niv[t[x]] && t[x] != root )
{
p_art[t[x]] = 1;
do
{
p = st.top();
st.pop();
c.push_back(p.second);
}while( (p.first != t[x] && p.second != x) && !st.empty());
c.push_back(p.first);
Cb.push_back(c);
c.clear();
}
}