Pagini recente » Cod sursa (job #821928) | Cod sursa (job #1667493) | Cod sursa (job #1494862) | Cod sursa (job #2314819) | Cod sursa (job #3041000)
///toata lumea baga azi biconexe
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream cin ("biconex.in");
ofstream cout ("biconex.out");
const int N = 1e5;
int discover[N + 1], low[N + 1], tata[N + 1];
int n, m, x, y, k;
vector <int> ans[N + 1];
vector <int> g[N + 1];
stack <int> s;
void dfs (int node, int time)
{
s.push(node);
discover[node] = low[node] = time;
for (auto it : g[node])
{
if (!discover[it])
{
tata[it] = node;
dfs (it, time + 1);
///verific daca e punct de articulatie
///practic verific daca fiul are sau nu un stramos
if (low[it] >= discover[node])
{
///facem comp biconexe
ans[++k].push_back(node);///punctul de articulatie
while (!s.empty() && s.top() != it)
{
ans[k].push_back(s.top());
s.pop();
}
ans[k].push_back(it);
if (!s.empty())
s.pop();
}
low[node] = min (low[node], low[it]);
}
else
{
///caut stramos
if (it != tata[node])
low[node] = min (low[node], discover[it]);
}
}
}
int main()
{
for (cin >> n >> m; m-- && cin >> x >> y; )
g[x].push_back(y), g[y].push_back(x);
dfs (1, 1);
cout << k << '\n';
for (int i = 1; i <= k; ++i, cout << '\n')
for (auto it : ans[i])
cout << it << ' ';
return 0;
}