Pagini recente » Cod sursa (job #2353029) | Cod sursa (job #83195) | Cod sursa (job #1492931) | Cod sursa (job #139300) | Cod sursa (job #2564604)
#include<fstream>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<vector<int> > components;
vector<int> G[100010];
int M[100010][2];
int viz[100010];
int nr = 0;
vector<int> stack;
void tarjan(int x, int f)
{
++nr;
viz[x] = 1;
M[x][0] = M[x][1] = nr;
stack.push_back(x);
for (auto& neighbor : G[x])
{
if (!viz[neighbor])
{
tarjan(neighbor, x);
if (M[x][0] <= M[neighbor][1])
{
vector<int> comp;
while (stack.back() != neighbor)
{
comp.push_back(stack.back());
stack.pop_back();
}
comp.push_back(neighbor);
comp.push_back(x);
stack.pop_back();
components.push_back(comp);
}
M[x][1] = min(M[x][1], M[neighbor][1]);
}
else if (neighbor != f)
{
M[x][1] = min(M[x][1], M[neighbor][0]);
}
}
}
int main()
{
int N, M;
in >> N >> M;
for (int i = 1; i <= M; ++i)
{
int x, y;
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
tarjan(1, 0);
out << components.size() << "\n";
for (auto& comp : components)
{
for (auto& node : comp)
{
out << node << " ";
}
out << "\n";
}
return 0;
}