Pagini recente » Cod sursa (job #1421091) | Cod sursa (job #2300469) | Cod sursa (job #2392649) | Cod sursa (job #3153476) | Cod sursa (job #1390302)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream is ("biconex.in");
ofstream os ("biconex.out");
const int Nmax = 100001;
const int INF = 0x3f3f3f3f;
int Nodes, Edges;
int Depth[Nmax], LowLink[Nmax];
vector <int> Graph[Nmax];
vector <vector<int>> BiconnectedComponents;
stack <int> Stk;
void Read();
void DFS(int node, int father, int level);
void Extract(int node);
int main()
{
Read();
DFS(1, 0, 1);
os << BiconnectedComponents.size() << '\n';
for (const auto& CurentBC : BiconnectedComponents)
{
for (const int& i : CurentBC)
os << i << ' ';
os << '\n';
}
is.close();
os.close();
}
void Read()
{
is >> Nodes >> Edges;
for (int x, y; Edges; --Edges)
{
is >> x >> y;
Graph[x].push_back(y);
Graph[y].push_back(x);
}
};
void DFS(int node, int father, int level)
{
Depth[node] = LowLink[node] = level;
Stk.push(node);
for (const int& next : Graph[node])
{
if (father == next)
continue;
if (Depth[next] == 0)
{
DFS(next, node, level+1);
LowLink[node] = min(LowLink[node], LowLink[next]);
if (LowLink[next] >= Depth[node])
Extract(node);
}
else
LowLink[node] = min(LowLink[node], Depth[next]);
}
};
void Extract(int node)
{
vector <int> CurentBC;
while (!Stk.empty() && node != Stk.top())
{
CurentBC.push_back(Stk.top());
Stk.pop();
}
CurentBC.push_back(Stk.top());
BiconnectedComponents.push_back(CurentBC);
};