Pagini recente » Cod sursa (job #1291816) | Cod sursa (job #1073033) | Cod sursa (job #1804727) | Cod sursa (job #2031369) | Cod sursa (job #2662745)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#include <tuple>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
using VI = vector<int>;
using SI = set<int>;
using VVI = vector<VI>;
int n, m, a, b;
int nv;
VVI G;
vector<SI> cbc;
SI c;
VI niv, L;
stack<pair<int, int>> stk;
void Tarjan(int nod, int tata);
int main()
{
fin >> n >> m;
G = VVI(n + 1);
niv = L = VI(n + 1);
for ( int i = 1; i <= m; ++i )
{
fin >> a >> b;
G[a].emplace_back(b);
G[b].emplace_back(a);
}
for ( int i = 1; i <= n; ++i )
if ( niv[i] == 0 )
Tarjan(i, 0);
fout << cbc.size() << "\n";
for (const auto& c : cbc)
{
for (const auto& x : c)
fout << x << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}
void Tarjan(int x, int tata)
{
niv[x] = L[x] = ++nv;
for ( const auto& y : G[x] )
{
if (y == tata) continue;
if ( niv[y] == 0 ) // muchie de arbore
{
stk.push({x, y});
Tarjan(y, x);
if (L[y] >= L[x])
{
c.clear();
int a, b;
while (true)
{
tie(a, b) = stk.top();
stk.pop();
c.insert(a); c.insert(b);
if (a == x && b == y)
break;
}
cbc.push_back(c);
}
L[x] = min(L[x], L[y]);
}
else // daca este back edge (nu exista cross edge la GN)
L[x] = min(L[x], niv[y]);
}
}