Pagini recente » Cod sursa (job #2903643) | Cod sursa (job #1106748) | Cod sursa (job #1073030) | Cod sursa (job #1457952) | Cod sursa (job #2590115)
#include <bits/stdc++.h>
int N, M;
std::vector <std::vector <int>> graph;
inline void addEdge(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
#define DETECT_ART false
#define DETECT_CRIT false
class BiconexCalculator {
public:
BiconexCalculator (std::vector <std::vector <int>> &graph) { calculate(graph); }
void calculate(std::vector <std::vector <int>> &graph) {
_time = 0;
nart = 0;
N = graph.size();
low .resize(graph.size(), 0);
disc.resize(graph.size(), 0);
if (DETECT_ART) art.resize (graph.size(), false);
for (int i=0; i<graph.size(); ++i)
if (!disc[i]) root = i, DFS(graph, i);
}
int getSize() { return components.size(); }
std::vector <std::vector <int>> getComponents() { return components; }
int getArticulationSize() { return nart; }
bool isArticulationPoint(int vertex) { return art[vertex]; }
std::vector <int> getArticulationPoints() {
std::vector <int> ans;
for (int i=0; i<N; ++i) if (art[i]) ans.push_back(i);
return ans;
}
int getCriticalSize() { return crit.size(); }
std::vector <std::pair <int, int>> getCriticalEdges() { return crit; }
std::vector <std::vector <int>> getBCCGraph(std::vector <std::vector <int>>& graph) {
std::vector <std::vector <int>> BCCGraph;
BCCGraph.resize(components.size());
std::vector <bool> seen(components.size(), false);
for (int i=0; i<components.size(); ++i) {
for (auto &u:components[i]) {
for (auto &it:graph[u])
if (comp[it] != i && !seen[comp[it]])
BCCGraph[i].push_back(comp[it]), seen[comp[it]] = true;
}
for (auto &it:BCCGraph[i]) seen[it] = false;
} return BCCGraph;
}
private:
void DFS(std::vector <std::vector <int>> &graph, int vertex, int parent = 0) {
disc[vertex] = low[vertex] = ++_time;
int children = 0;
for (auto &it:graph[vertex]) {
if (it == parent) continue;
if (!disc[it]) {
++ children;
stack.push({vertex, it});
DFS(graph, it, vertex);
low[vertex] = std::min(low[vertex], low[it]);
if (low[it] >= disc[vertex]) {
if (vertex != root) addArticulationPoint(vertex);
if (low[it] > disc[vertex]) addCriticalEdge(it, vertex);
addComponent(vertex);
}
} else low[vertex] = std::min(low[vertex], disc[it]);
}
if (vertex == root && children > 1) addArticulationPoint(vertex);
}
void addArticulationPoint(int vertex) { if (DETECT_ART) nart += !art[vertex], art[vertex] = true; }
void addCriticalEdge (int u, int v) { if (DETECT_CRIT) crit.push_back({u, v}); }
void addComponent (int vertex) {
components.push_back(std::vector <int> ());
while (stack.top().first != vertex) {
components.back().push_back(stack.top().second);
stack.pop();
} components.back().push_back(stack.top().second); components.back().push_back(stack.top().first);
stack.pop();
}
int _time, root;
int N, nart;
std::vector <int> low, disc, comp;
std::vector <std::vector <int>> components;
std::vector <std::pair <int, int>> crit;
std::vector <bool> art;
std::stack <std::pair <int, int>> stack;
};
std::ifstream input ("biconex.in");
std::ofstream output("biconex.out");
int main()
{
input >> N >> M;
graph.resize(N, std::vector <int>());
for (int i=0, u, v; i<M; ++i) input >> u >> v, addEdge(u-1, v-1);
BiconexCalculator calc(graph);
output << calc.getSize() << '\n';
for (auto &it:calc.getComponents()) {
for (auto &it2:it) output << it2+1 << ' ';
output << '\n';
}
return 0;
}