Pagini recente » Cod sursa (job #2593420) | Cod sursa (job #1516754) | Cod sursa (job #1537685) | Cod sursa (job #2462006) | Cod sursa (job #2464900)
#include <unordered_map>
#include <vector>
#include <fstream>
#include <stack>
#include <algorithm>
using std::vector;
using std::unordered_map;
using std::stack;
struct Vertex {
using IndexType = int;
IndexType id;
vector<IndexType> outEdges;
static constexpr IndexType UndefinedIndex = -1;
IndexType index = UndefinedIndex;
IndexType lowLink = UndefinedIndex;
bool onStack = false;
};
struct Graph {
using VertexIdx = Vertex::IndexType;
unordered_map<VertexIdx, Vertex> vertices;
template<typename T>
static Graph fromStrean(T& stream) {
int n, m;
stream >> n >> m;
Graph ret;
for (int i = 0; i < m; ++i) {
VertexIdx a, b;
stream >> a >> b;
ret.vertices[a].id = a;
ret.vertices[b].id = b;
ret.vertices[a].outEdges.push_back(b);
}
return ret;
}
using StrongConnectComponent = vector<VertexIdx>;
using TarjanSol = vector<StrongConnectComponent>;
TarjanSol tarjan() {
TarjanSol sol;
VertexIdx index = 0;
stack<VertexIdx> s;
for(auto& it : vertices) {
Vertex& v = it.second;
if (v.index == Vertex::UndefinedIndex) {
strongConnect(sol, v, index, s);
}
}
return sol;
}
void strongConnect(TarjanSol& sol, Vertex& v, VertexIdx& index, stack<VertexIdx>& s) {
v.index = index;
v.lowLink = index;
++index;
s.push(v.id);
v.onStack = true;
for (VertexIdx idx : v.outEdges) {
Vertex& w = vertices[idx];
if (w.index == Vertex::UndefinedIndex) {
strongConnect(sol, w, index, s);
if (v.lowLink != Vertex::UndefinedIndex) {
v.lowLink = std::min(v.lowLink, w.lowLink);
} else {
v.lowLink = w.lowLink;
}
} else if (w.onStack) {
if (v.lowLink != Vertex::UndefinedIndex) {
v.lowLink = std::min(v.lowLink, w.index);
} else {
v.lowLink = w.index;
}
}
}
if (v.lowLink == v.index) {
StrongConnectComponent scc;
while(s.top() != v.id) {
Vertex& w = vertices[s.top()];
s.pop();
w.onStack = false;
scc.push_back(w.id);
}
s.pop();
v.onStack = false;
scc.push_back(v.id);
sol.emplace_back(std::move(scc));
}
}
};
int main()
{
std::ifstream fin("ctc.in");
std::ofstream fout("ctc.out");
Graph g = Graph::fromStrean(fin);
const auto solutions = g.tarjan();
fout << solutions.size() << "\n";
for (const auto& solution: solutions) {
for (const auto id: solution) {
fout << id << " ";
}
fout << "\n";
}
return 0;
}