Pagini recente » Cod sursa (job #2845556) | Cod sursa (job #1161522) | Cod sursa (job #2241893) | Cod sursa (job #2560175) | Cod sursa (job #2197801)
#include <algorithm>
#include <fstream>
#include <stack>
#include <utility>
#include <vector>
void bcGet(std::stack<std::pair<unsigned, unsigned>>& edgeStack, std::pair<unsigned, unsigned> edge, std::vector<std::vector<unsigned>>& components) {
std::pair<unsigned, unsigned> current;
do {
current = edgeStack.top();
edgeStack.pop();
components[components.size() - 1].push_back(current.first);
components[components.size() - 1].push_back(current.second);
} while(current.first != edge.first || current.second != edge.second);
std::vector<unsigned>& lastComponent = components[components.size() - 1];
std::sort(lastComponent.begin(), lastComponent.end());
lastComponent.resize(std::unique(lastComponent.begin(), lastComponent.end()) - lastComponent.begin());
}
void bcDFS(unsigned u, std::vector<std::vector<unsigned>>& graph, std::vector<bool>& visited, std::vector<unsigned>& disc,
std::vector<unsigned>& low, std::vector<int>& parent, std::vector<std::vector<unsigned>>& components, std::stack<std::pair<unsigned, unsigned>>& edgeStack) {
static int time = 0;
time++;
visited[u - 1] = true;
disc[u - 1] = time;
low[u - 1] = time;
for (unsigned v : graph[u - 1]) {
if (!visited[v - 1]) {
parent[v - 1] = u;
edgeStack.push(std::make_pair(u, v));
bcDFS(v, graph, visited, disc, low, parent, components, edgeStack);
low[u - 1] = std::min(low[u - 1], low[v - 1]);
if (low[v - 1] >= disc[u - 1]) {
components.push_back(std::vector<unsigned>());
bcGet(edgeStack, std::make_pair(u, v), components);
}
} else if (parent[v - 1] != u && disc[v - 1] < disc[u - 1]) {
edgeStack.push(std::make_pair(u, v));
low[u - 1] = std::min(low[u - 1], disc[v - 1]);
}
}
}
int main() {
std::ifstream in("biconex.in");
std::ofstream out("biconex.out");
unsigned n, m;
in >> n >> m;
std::vector<std::vector<unsigned>> graph = std::vector<std::vector<unsigned>>();
graph.reserve(n);
for (unsigned i = 0; i < n; i++) graph.push_back(std::vector<unsigned>());
for (unsigned i = 0 ; i < m; i++) {
unsigned v1, v2;
in >> v1 >> v2;
graph[v1 - 1].push_back(v2);
graph[v2 - 1].push_back(v1);
}
std::vector<bool> visited = std::vector<bool>();
visited.reserve(n);
for (unsigned i = 0; i < n; i++) visited.push_back(false);
std::vector<unsigned> disc = std::vector<unsigned>();
disc.reserve(n);
for (unsigned i = 0; i < n; i++) disc.push_back(0);
std::vector<unsigned> low = std::vector<unsigned>();
low.reserve(n);
for (unsigned i = 0; i < n; i++) low.push_back(0);
std::vector<int> parent = std::vector<int>();
parent.reserve(n);
for (unsigned i = 0; i < n; i++) parent.push_back(-1);
std::vector<std::vector<unsigned>> components = std::vector<std::vector<unsigned>>();
std::stack<std::pair<unsigned, unsigned>> edgeStack = std::stack<std::pair<unsigned, unsigned>>();
for (unsigned i = 0; i < n; i++) {
if (!visited[i]) bcDFS(i + 1, graph, visited, disc, low, parent, components, edgeStack);
}
out << components.size() << "\n";
for (auto c : components) {
for (unsigned v : c) {
out << v << " ";
}
out << "\n";
}
return 0;
}