Pagini recente » Cod sursa (job #152441) | Cod sursa (job #2521917) | Cod sursa (job #1296504) | Cod sursa (job #1982676) | Cod sursa (job #3225949)
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
class Solutuion {
private:
size_t N;
size_t M;
vector<vector<size_t>> adj;
vector<size_t> start;
vector<set<size_t>> biconex;
vector<size_t> parents;
stack<size_t> s;
size_t time = 0;
size_t dfs(size_t root, size_t node) {
start[node] = ++time;
s.push(node);
size_t min_node = node;
bool has_2_children = false;
for (auto neigh : adj[node]) {
if (neigh == parents[node])
continue;
if (start[neigh] == 0) {
parents[neigh] = node;
size_t rez = dfs(root, neigh);
if (!has_2_children) {
for (auto neigh : adj[node]) {
if (start[neigh] == 0) {
has_2_children = true;
break;
}
}
}
if ((start[rez] >= start[node] && node != root) ||
(node == root && has_2_children)) {
while (s.top() != neigh) {
biconex.back().insert(s.top());
s.pop();
}
biconex.back().insert(neigh);
s.pop();
biconex.back().insert(node);
biconex.push_back(set<size_t>());
continue;
}
if (start[node] > start[rez]) {
if (start[min_node] > start[rez])
min_node = rez;
}
} else if (start[node] > start[neigh]) {
if (start[min_node] > start[neigh])
min_node = neigh;
}
}
if (node == root)
biconex.pop_back();
return min_node;
}
public:
explicit Solutuion(ifstream &in) {
in >> N >> M;
adj.resize(N + 1);
start.resize(N + 1, 0);
parents.resize(N + 1, 0);
size_t node1, node2;
for (size_t i = 1; i <= M; i++) {
in >> node1 >> node2;
adj[node1].push_back(node2);
adj[node2].push_back(node1);
}
}
vector<set<size_t>> solve() {
bool end = false;
size_t source;
while (!end) {
end = true;
for (size_t node = 1; node <= N; node++)
if (start[node] == 0) {
source = node;
end = false;
biconex.push_back(set<size_t>());
dfs(source, source);
break;
}
}
return biconex;
}
};
int main() {
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<set<size_t>> solution = Solutuion(in).solve();
out << solution.size() << endl;
for (auto sol : solution) {
copy(sol.begin(), sol.end(), ostream_iterator<size_t>(out, " "));
out << endl;
}
in.close();
out.close();
return 0;
}