Pagini recente » Cod sursa (job #401982) | Cod sursa (job #1388938) | Cod sursa (job #1354273) | Cod sursa (job #2653561) | Cod sursa (job #1117134)
#include <algorithm>
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
typedef pair<int, int> Edge;
const int INF = 1 << 30;
const int MAX_N = 100100;
int N, M;
vector<int> graph[MAX_N];
vector<vector<int>> biconex;
stack<Edge> edge_stack;
int depth[MAX_N];
int lowest[MAX_N];
bool visited[MAX_N];
void read_input();
void dfs(int node);
void print_output();
void get_component(const Edge &start);
int main() {
read_input();
dfs(1);
print_output();
return 0;
}
void read_input() {
fin >> N >> M;
for (int i = 1, a, b; i <= M; i += 1) {
fin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
}
void dfs(int node) {
visited[node] = true;
lowest[node] = depth[node];
for (auto son: graph[node]) {
if (visited[son]) {
lowest[node] = min(lowest[node], depth[son]);
continue;
}
depth[son] = depth[node] + 1;
edge_stack.push(make_pair(node, son));
dfs(son);
if (lowest[son] >= depth[node]) {
get_component(make_pair(node, son));
}
lowest[node] = min(lowest[node], lowest[son]);
}
}
void get_component(const Edge &start) {
biconex.push_back(vector<int>());
vector<int> &c = biconex.back();
while (edge_stack.top() != start) {
c.push_back(edge_stack.top().first);
c.push_back(edge_stack.top().second);
edge_stack.pop();
}
c.push_back(edge_stack.top().first);
c.push_back(edge_stack.top().second);
edge_stack.pop();
sort(c.begin(), c.end());
c.resize(unique(c.begin(), c.end()) - c.begin());
}
void print_output() {
fout << biconex.size() << '\n';
for (auto c: biconex) {
for (auto i: c) {
fout << i << ' ';
}
fout << '\n';
}
}