Pagini recente » Cod sursa (job #1447258) | Cod sursa (job #1627585) | Cod sursa (job #1092761) | Cod sursa (job #2443324) | Cod sursa (job #1571788)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define MaxNodes 100001
ifstream is("biconex.in");
ofstream os("biconex.out");
int n, m, x1, x2;
vector<vector<int> > G, comp;
vector<int> c;
stack<pair<int, int> > s;
int nv[MaxNodes];
int l[MaxNodes];
bool v[MaxNodes];
void Read();
void Df(int x, int t, int niv);
void Write();
int main()
{
Read();
Df(1, 0, 0);
Write();
is.close();
os.close();
return 0;
}
void Read()
{
G = vector<vector<int> >(MaxNodes);
is >> n >> m;
for ( int i = 1, x, y; i <= m; ++i )
{
is >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void Df(int x, int t, int niv)
{
nv[x] = l[x] = niv;
v[x] = true;
for ( const auto& y : G[x] )
{
if ( y == t ) continue;
if ( !v[y] )
{
s.push({x, y});
Df(y, x, niv + 1);
l[x] = min(l[x], l[y]);
if ( l[y] >= nv[x] )
{
c.clear();
do
{
x1 = s.top().first;
x2 = s.top().second;
s.pop();
c.push_back(x1);
c.push_back(x2);
} while ( x1 != x && x2 != y );
comp.push_back(c);
}
}
else
l[x] = min(l[x], nv[y]);
}
}
void Write()
{
os << comp.size() << '\n';
for ( auto& c : comp )
{
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
for ( const auto& t : c )
os << t << ' ';
os << '\n';
}
}