Pagini recente » Cod sursa (job #1555538) | Cod sursa (job #1598702) | Cod sursa (job #1968379) | Cod sursa (job #2232352) | Cod sursa (job #1790598)
#include <fstream>
#include <vector>
using namespace std;
struct Nod
{
int timp;
int timp_min;
vector<int> vecini;
};
typedef vector<Nod> Graf;
typedef pair<int, int> Muchie;
int TIMP = 0;
vector<int> ExtrageComponenta(vector<Muchie> &st, const Muchie &m)
{
vector<int> comp;
while (st.back() != m) {
comp.push_back(st.back().second);
st.pop_back();
}
comp.push_back(m.second);
comp.push_back(m.first);
st.pop_back();
return comp;
}
void Tarjan(Graf &g, int nod, vector<Muchie> &st, vector<vector<int>> &comp)
{
g[nod].timp = g[nod].timp_min = ++TIMP;
for (int vecin : g[nod].vecini) {
if (g[vecin].timp == 0) {
st.push_back({nod, vecin});
Tarjan(g, vecin, st, comp);
g[nod].timp_min = min(g[nod].timp_min, g[vecin].timp_min);
if (g[vecin].timp_min >= g[nod].timp)
comp.push_back(ExtrageComponenta(st, {nod, vecin}));
}
g[nod].timp_min = min(g[nod].timp_min, g[vecin].timp);
}
}
vector<vector<int>> AflaComponente(Graf &g)
{
for (auto &nod : g)
nod.timp = nod.timp_min = 0;
vector<vector<int>> comp;
vector<Muchie> stiva;
Tarjan(g, 1, stiva, comp);
return comp;
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
fin >> n >> m;
Graf graf(n + 1);
while (m--) {
int x, y;
fin >> x >> y;
graf[x].vecini.push_back(y);
graf[y].vecini.push_back(x);
}
auto componente = AflaComponente(graf);
fout << componente.size() << "\n";
for (auto &comp : componente) {
for (int nod : comp)
fout << nod << " ";
fout << "\n";
}
return 0;
}