Pagini recente » Cod sursa (job #2732470) | Cod sursa (job #1742151) | Cod sursa (job #1671126) | Cod sursa (job #1822604) | Cod sursa (job #1921011)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
fstream fin ("biconex.in", ios::in), fout ("biconex.out", ios::out);
int n, m, low[100010], dfn[100010];
vector < int > G[100010];
vector < vector < int > > Sol;
vector < bool > F(100010);
stack < int > S;
inline int Minim(const int &a, const int &b)
{
if (a < b) return a;
return b;
}
void Add_Biconex_Component(int pct_art)
{
Sol.push_back(vector < int > ());
while (S.top() != pct_art)
{
Sol[Sol.size() - 1].push_back(S.top());
S.pop();
}
Sol[Sol.size() - 1].push_back(pct_art);
}
void Biconex(int node, int level)
{
dfn[node] = low[node] = level;
F[node] = true;
S.push(node);
for (auto it : G[node])
{
if (F[it])
{
low[node] = Minim(low[node], dfn[it]);
}
else
{
Biconex(it, level + 1);
low[node] = Minim(low[node], low[it]);
if (low[it] >= level) Add_Biconex_Component(node);
}
}
}
int main()
{
fin >> n >> m;
for (int i = 1, x, y; i <= m; i ++)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
Biconex(1, 0);
fout << Sol.size() << '\n';
for (auto it1 : Sol)
{
for (auto it2 : it1)
{
fout << it2 << ' ';
}
fout << '\n';
}
fout.close();
return 0;
}