Pagini recente » Cod sursa (job #1004585) | Cod sursa (job #1003203) | Cod sursa (job #2555828) | Cod sursa (job #2089048) | Cod sursa (job #2161949)
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
const int Dim = 1e5 + 5;
int m, n, K; // K - nr comp biconexe
vector <int> G[Dim];
int niv[Dim], L[Dim];
stack <pair<int, int> > s;
set<int> comp[Dim];
void Extract(int x, int y)
{
int xs, ys;
do
{
xs = s.top().first; ys = s.top().second;
comp[K].insert (xs);
comp[K].insert (ys);
s.pop();
} while (xs != x || ys != y);
}
int nv;
void Dfs(int x, int tata)
{
L[x] = niv[x] = ++nv;
for (const int& y : G[x])
{
if (y == tata)
continue;
if (!niv[y]) // fiu nevizitat
{
s.push ({x, y});
Dfs (y, x);
L[x] = min(L[x], L[y]);
if (L[y] >= niv[x])
K++, Extract(x, y);
}
else
L[x] = min(L[x], niv[y]);
}
}
int main()
{
fin >> n >> m;
for (int x, y, i = 0; i < m; ++i)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
Dfs (1, 0);
fout << K << "\n";
for (int i = 1; i <= K; ++i)
{
for (const int& node : comp[i])
fout << node << " ";
fout << "\n";
}
}