Pagini recente » Istoria paginii utilizator/mocke | Cod sursa (job #102282) | Cod sursa (job #2592156) | Cod sursa (job #783104) | Cod sursa (job #779613)
Cod sursa(job #779613)
#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);
}
}
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<int> comp;
while (!edge_stack.empty() && edge_stack.top() != make_pair(father[node], node)) {
pair<int, int> edge = edge_stack.top();
edge_stack.pop();
comp.push_back(edge.first);
comp.push_back(edge.second);
}
sort(comp.begin(), comp.end());
comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
sol.push_back(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();
}