Pagini recente » Cod sursa (job #1743992) | Cod sursa (job #1136843) | Cod sursa (job #489534) | Cod sursa (job #1815174) | Cod sursa (job #1389778)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream is ("biconex.in");
ofstream os ("biconex.out");
const int Nmax = 100001;
const int oo = 0x3f3f3f3f;
int N, M;
int Ind[Nmax]; //Ind[i] = adancimea nodului i in arborele DF
int L[Nmax]; //L[i] = cea mai mica adancime a vecinilor nodului i
bool Viz[Nmax];
vector <int> G[Nmax], Comp;
vector < vector<int> > BCC;
stack <int> S;
void Read();
void DFS(int node);
void Biconnected(int node);
int main()
{
Read();
DFS(1);
Biconnected(1);
os << BCC.size();
os << '\n';
for (const auto& C : BCC)
{
for (const int& i : C)
os << i << ' ';
os << '\n';
}
is.close();
os.close();
}
void Read()
{
is >> N >> M;
for (int i = 1, a, b; i <= M; ++i)
{
is >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
for (int i = 1; i <= N; ++i)
L[i] = oo;
};
int ActualDepth;
void DFS(int node)
{
Viz[node] = 1;
Ind[node] = ++ActualDepth;
for (const int& next : G[node])
if (Ind[next] == 0)
{
DFS(next);
L[node] = min(L[node], L[next]);
}
else
L[node] = min(L[node], Ind[next]);
--ActualDepth;
};
void Biconnected(int node)
{
Viz[node] = 0;
S.push(node);
for (const int& next : G[node])
if (Viz[next])
{
Biconnected(next);
if (L[next] >= Ind[node])
{
Comp.clear();
for (;!S.empty() && S.top() != next; S.pop())
Comp.push_back(S.top());
Comp.push_back(S.top()), S.pop();
Comp.push_back(node);
BCC.push_back(Comp);
}
}
};