Pagini recente » Rezultatele filtrării | onis-2016/solutii-runda-1 | Borderou de evaluare (job #2256522) | Cod sursa (job #1708975) | Cod sursa (job #3209200)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int task;
int numberOfVertices, numberOfEdges;
int root = 1;
int sonsOfRoot;
vector <vector <int>> graph;
vector <bool> visited;
vector <int> level, minimumLevel;
stack <pair <int, int>> edgeStack;
vector <unordered_set <int>> biconnectedComponents;
void initializeContainers() {
graph = vector <vector <int>>(numberOfVertices + 1);
visited = vector <bool>(numberOfVertices + 1, false);
level = vector <int>(numberOfVertices + 1);
minimumLevel = vector <int>(numberOfVertices + 1);
}
void readData() {
fin >> numberOfVertices >> numberOfEdges;
initializeContainers();
int x, y;
while (numberOfEdges--) {
fin >> x >> y;
graph[x].emplace_back(y);
graph[y].emplace_back(x);
}
}
void extractBiconnectedComponent(int node, int neighbour) {
unordered_set <int> biconnectedComponent;
pair <int, int> edge;
do {
edge = edgeStack.top();
edgeStack.pop();
biconnectedComponent.insert(edge.first);
biconnectedComponent.insert(edge.second);
} while (edge.first != node && edge.second != neighbour);
biconnectedComponents.emplace_back(biconnectedComponent);
}
void dfs(int node, int father) {
visited[node] = true;
level[node] = level[father] + 1;
minimumLevel[node] = level[father] + 1;
for (const int& neighbour: graph[node]) {
if (neighbour == father) {
continue;
}
if (visited[neighbour]) {
minimumLevel[node] = min(minimumLevel[node], level[neighbour]);
}
else {
if (node == root) {
++sonsOfRoot;
}
edgeStack.emplace(node, neighbour);
dfs(neighbour, node);
minimumLevel[node] = min(minimumLevel[node], minimumLevel[neighbour]);
if (minimumLevel[neighbour] >= level[node]) {
extractBiconnectedComponent(node, neighbour);
}
}
}
}
void printBiconnectedComponents() {
fout << biconnectedComponents.size() << '\n';
for (const auto& biconnectedComponent: biconnectedComponents) {
for (const int& node: biconnectedComponent) {
fout << node << ' ';
}
fout << '\n';
}
}
int main()
{
readData();
dfs(root, 0);
printBiconnectedComponents();
return 0;
}