Pagini recente » Cod sursa (job #786900) | Cod sursa (job #1889138) | Cod sursa (job #1345527) | Cod sursa (job #757174) | Cod sursa (job #1390332)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
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 < set<int> > BiconnectedComponents;
stack < pair<int, int> > Stk;
void Read();
void DFS(int node, int father, int level);
void Extract(int node, int next);
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;
for (const int& next : Graph[node])
{
if (father == next)
continue;
if (Depth[next] == 0)
{
Stk.push({node, next});
DFS(next, node, level+1);
LowLink[node] = min(LowLink[node], LowLink[next]);
if (LowLink[next] >= Depth[node])
Extract(node, next);
}
else
LowLink[node] = min(LowLink[node], Depth[next]);
}
};
void Extract(int node, int next)
{
set <int> CurentBC;
int X, Y;
do
{
X = Stk.top().first;
Y = Stk.top().second;
Stk.pop();
CurentBC.insert(X);
CurentBC.insert(Y);
}
while (!Stk.empty() && node != X && next != Y);
BiconnectedComponents.push_back(CurentBC);
};