Pagini recente » Cod sursa (job #1030732) | Cod sursa (job #417032) | Cod sursa (job #1552876) | Cod sursa (job #2103555) | Cod sursa (job #2932053)
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
vector <int> graph[100005];
bool visited[100005];
vector <int> chain;
int highestLevel[100005];
int level[100005];
vector <vector <int>> biconex;
void DFS(int node, int parent) {
visited[node] = true;
level[node] = level[parent] + 1;
highestLevel[node] = level[node];
chain.push_back(node);
for (int newNode : graph[node]) {
if (newNode == parent) {
continue;
}
if (visited[newNode]) {
highestLevel[node] = min(highestLevel[node], level[newNode]);
continue;
}
DFS(newNode, node);
highestLevel[node] = min(highestLevel[node], highestLevel[newNode]);
if (highestLevel[newNode] >= level[node]) {
vector <int> temp;
while (!chain.empty() && chain.back() != newNode) {
temp.push_back(chain.back());
chain.pop_back();
}
temp.push_back(newNode);
chain.pop_back();
temp.push_back(node);
biconex.push_back(temp);
}
}
}
int main() {
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);
}
for (int i = 1; i <= n; i++) {
if (visited[i]) {
continue;
}
DFS(i, 0);
}
fout << biconex.size() << '\n';
for (auto x : biconex) {
for (auto y : x) {
fout << y << ' ';
}
fout << '\n';
}
}