Pagini recente » Monitorul de evaluare | Cod sursa (job #2983703) | Cod sursa (job #205369) | Cod sursa (job #1947345) | Cod sursa (job #3233973)
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
class Solutuion {
private:
unsigned long long N;
unsigned long long M;
vector<vector<unsigned long long>> adj;
vector<unsigned long long> start;
vector<unsigned long long> parent;
vector<unsigned long long> low_link;
vector<set<unsigned long long>> bicon;
stack<pair<unsigned long long, unsigned long long>> st;
unsigned long long time;
void dfs(unsigned long long node) {
start[node] = ++time;
low_link[node] = time;
for (auto neigh : adj[node]) {
if (neigh == parent[node])
continue;
if (start[neigh] == 0) {
st.push({node, neigh});
parent[neigh] = node;
dfs(neigh);
if (low_link[neigh] >= start[node]) {
bicon.push_back(set<unsigned long long>());
while (true) {
auto top = st.top();
bicon.back().insert(top.first);
bicon.back().insert(top.second);
if (top.first != node) {
st.pop();
} else {
st.pop();
break;
}
}
}
}
low_link[node] = min(low_link[node], low_link[neigh]);
}
}
void dfs_root(unsigned long long root) {
start[root] = ++time;
low_link[root] = time;
for (auto neigh : adj[root]) {
if (start[neigh] == 0) {
st.push({root, neigh});
parent[neigh] = root;
dfs(neigh);
bicon.push_back(set<unsigned long long>());
while (true) {
auto top = st.top();
bicon.back().insert(top.first);
bicon.back().insert(top.second);
if (top.first != root) {
st.pop();
} else {
st.pop();
break;
}
}
}
}
st.pop();
}
public:
explicit Solutuion(ifstream &in) {
in >> N >> M;
adj.resize(N + 1);
start.resize(N + 1, 0);
parent.resize(N + 1, 0);
low_link.resize(N + 1, 0);
unsigned long long node1, node2;
for (unsigned long long i = 1; i <= M; i++) {
in >> node1 >> node2;
adj[node1].push_back(node2);
adj[node2].push_back(node1);
}
}
vector<set<unsigned long long>> solve() {
for (unsigned long long node = 1; node <= N; node++)
if (start[node] == 0) {
time = 0;
dfs_root(node);
}
return bicon;
}
};
int main() {
ifstream in("biconex.in");
ofstream out("biconex.out");
auto solution = Solutuion(in).solve();
out << solution.size() << endl;
for (auto sol : solution) {
copy(sol.begin(), sol.end(), ostream_iterator<unsigned long long>(out, " "));
out << endl;
}
in.close();
out.close();
return 0;
}