Pagini recente » Cod sursa (job #2353631) | Cod sursa (job #2097496) | Cod sursa (job #756167) | Cod sursa (job #2353745) | Cod sursa (job #1534627)
#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<int> st;
void Read();
void Tarjan(int x, int nv);
void Mark();
int main()
{
Read();
root = 1;
Tarjan(root, 1);
int x, y;
Mark();
while(!st.empty())
{
x = st.top();
st.pop();
y = p_art[t[x]];
c.push_back(x);
if( y == 1 )
{
c.push_back(t[x]);
Cb.push_back(c);
c.clear();
}
}
if ( c.size() != 1 )
Cb.push_back(c);
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++;
st.push(x);
L[x] = niv[x] = nv;
for ( auto y : G[x] )
{
if ( !niv[y] )
{
t[y] = x;
Tarjan(y, nv + 1);
L[x] = min(L[y], L[x]);
}
else
if ( t[x] != y )
L[x] = min(L[x], niv[y]);
}
}
void Mark()
{
for ( int i = 1; i <= n; i++ )
{
if ( !t[i] )
{
if ( nr > 1)
p_art[i] = 1;
//fout << i << ' ';
continue;
}
if ( L[i] >= niv[t[i]] && t[i] != root )
{
p_art[t[i]] = 1;
//, fout << i << ' ';
}
}
//fout << "tati:\n";
// int i;
// for ( i = 1; i <= n; i++ )
// fout << t[i] << " ";
//
// fout << "\nniv\n";
// for ( i = 1; i <= n; i++ )
// fout << niv[i] << " ";
//
// fout << "\nl:\n";
// for ( i = 1; i <= n; i++ )
// fout << L[i] << " ";
// fout << "\n";
//
// fout << "punctele de articulatie:\n";
// for ( i = 1; i <= n; i++ )
// if ( p_art[i] ) fout << i << " ";
}