Pagini recente » Cod sursa (job #1631336) | Cod sursa (job #840435) | Cod sursa (job #2174844) | Cod sursa (job #2225851) | Cod sursa (job #1390372)
/// prima parte e problema clasica a componentelor biconexe,
/// dupaia urmeaza niste functii care gasesc punctele de articulatie si muchiile critice
#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);
/// ADD-ONS
int Father[Nmax], RootSons;
vector <int> Articulation();
vector < pair<int, int> > Bridges();
///
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';
}
os << '\n' << '\n';
vector <int> PA = Articulation();
for (const int& i : PA)
os << i << ' ';
os << '\n' << '\n';
vector < pair<int, int> > CE = Bridges();
for (const auto& i : CE)
os << i.first << ' ' << i.second << '\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)
{
if (level == 2) RootSons++; ///ADD-ON
Depth[node] = LowLink[node] = level;
for (const int& next : Graph[node])
{
if (father == next)
continue;
if (Depth[next] == 0)
{
Father[next] = node; ///ADD-ON
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);
};
/// ADD-ONS
vector <int> Articulation()
{
bool Art[Nmax];
vector <int> Sol;
if (RootSons > 1) Art[1] = 1;
for (int i = 2; i <= Nodes; ++i)
if (Father[i] != 1 && LowLink[i] >= Depth[Father[i]])
Art[Father[i]] = 1;
for (int i = 1; i <= Nodes; ++i)
if (Art[i] == 1)
Sol.push_back(i);
return Sol;
};
vector < pair<int, int> > Bridges()
{
vector <pair<int,int> > Sol;
for (int i = 2; i <= Nodes; ++i) //sarim peste nodul 1 ptr ca nu are tata
if (LowLink[i] > Depth[Father[i]])
Sol.push_back({Father[i], i});
return Sol;
};
///