Pagini recente » Cod sursa (job #2632160) | Cod sursa (job #2449888) | Cod sursa (job #3185239) | Lista propunatori infoarena-friendly | Cod sursa (job #779615)
Cod sursa(job #779615)
#include <algorithm>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
#define FORIT(it, v) for (typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
const int MAX_N = 100005;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
vector<int> graph[MAX_N];
bool vis[MAX_N];
int father[MAX_N];
int level[MAX_N];
int up[MAX_N];
stack< pair<int, int> > edge_stack;
vector< vector<int> > sol;
void read() {
fin >> n >> m;
for (int i = 0; i < m; ++i) {
int a, b;
fin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
}
vector<int> unique_vals(vector< pair<int, int> > v) {
vector<int> vals;
FORIT(it, v) {
vals.push_back(it->first);
vals.push_back(it->second);
}
sort(vals.begin(), vals.end());
vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
return vals;
}
void dfs(int node) {
vis[node] = true;
up[node] = level[node];
FORIT(it, graph[node])
if (!vis[*it]) {
father[*it] = node;
level[*it] = level[node] + 1;
edge_stack.push(make_pair(node, *it));
dfs(*it);
// check dp
up[node] = min(up[node], up[*it]);
// new biconnected component found
if (up[*it] >= level[node]) {
vector< pair<int, int> > comp;
while (edge_stack.top() != make_pair(node, *it)) {
comp.push_back(edge_stack.top());
edge_stack.pop();
}
comp.push_back(edge_stack.top());
edge_stack.pop();
sol.push_back(unique_vals(comp));
}
} else {
// check dp
if (level[*it] < level[node] - 1)
up[node] = min(up[node], level[*it]);
}
}
void write() {
fout << sol.size() << "\n";
FORIT(it, sol) {
FORIT(it2, *it)
fout << *it2 << " ";
fout << "\n";
}
}
int main() {
read();
dfs(1);
write();
}