Pagini recente » Cod sursa (job #889982) | Profil rusurares111 | Cod sursa (job #2081049) | Cod sursa (job #2235630) | Cod sursa (job #2102473)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
const int Inf = 0x3f3f3f3f;
VVI G, f, comp;
VI niv, t, st, L;
VB v;
stack<int> stk;
int n, m, nr;
void ReadGraph();
void Df(int x);
void WriteComponents();
int main()
{
ReadGraph();
Df(1);
WriteComponents();
fin.close();
fout.close();
return 0;
}
void WriteComponents()
{
int cnt;
fout << nr << '\n';
for (int i = 1; i <= nr; ++i )
{
cnt = comp[i].size();
for (const auto& j : comp[i] )
fout << j << ' ';
fout << t[comp[i][cnt - 1]] << '\n';
}
}
void Df(int x)
{
v[x] = true;
niv[x] = niv[t[x]] + 1;
for (const auto& y : G[x])
{
if ( !v[y] )
{
t[y] = x;
f[x].push_back(y);
stk.push(y);
Df(y);
if ( L[y] >= niv[x] )
{
++nr;
while ( stk.top() != y )
{
comp[nr].push_back(stk.top());
stk.pop();
}
comp[nr].push_back(stk.top());
stk.pop();
}
}
}
int mi = Inf;
for (const auto& y : f[x] )
mi = min(mi, L[y]);
for (const auto& y : G[x] )
mi = min(mi, niv[y]);
L[x] = mi;
}
void ReadGraph()
{
fin >> n >> m;
G = f = comp = VVI(n + 1);
niv = t = st = L = VI(n + 1);
v = VB(n + 1);
int x, y;
while (m--)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}