Pagini recente » Cod sursa (job #146193) | Cod sursa (job #119640) | Cod sursa (job #336335) | Cod sursa (job #1887497) | Cod sursa (job #2723356)
/*
low[node] = cel mai mic nivel pe care putem ajunge din node mergand in jos pe arborele DFS si apoi in sus
pe muchii de intoarcere
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMax = 1e5;
vector <int> g[NMax + 5], answer[NMax + 5];
stack <pair <int, int>> st;
int n, m, number;
int level[NMax + 5], low[NMax + 5];
bool use[NMax + 5];
void Read(){
fin >> n >> m;
while (m--){
int x, y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
}
void DFS(int node, int father){
use[node] = 1;
level[node] = low[node] = level[father] + 1;
for (auto ngh : g[node]){
if (use[ngh])
low[node] = min(low[node], level[ngh]);
if (ngh == father || use[ngh])
continue;
st.push({node, ngh});
DFS(ngh, node);
if (low[ngh] >= level[node]){
number++;
bool ok = 1;
while (ok){
pair <int, int> edge = st.top();
st.pop();
int node1 = edge.first, node2 = edge.second;
if (node1 == node && node2 == ngh)
ok = 0;
answer[number].push_back(node2);
}
answer[number].push_back(node);
}
low[node] = min(low[node], low[ngh]);
}
}
void Print(){
fout << number << '\n';
for (int i = 1; i <= number; i++){
for (auto node : answer[i])
fout << node << ' ';
fout << '\n';
}
}
int main(){
Read();
DFS(1, 0);
Print();
return 0;
}