Pagini recente » Cod sursa (job #3285855) | Cod sursa (job #3292864) | Cod sursa (job #3294082) | Cod sursa (job #3293307) | Cod sursa (job #3293843)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N,M;
vector<bool> isVisited(100005, false);
vector<int> tin(100005);
vector<int> low(100005);
vector<vector<int>> graph(100005, vector<int>());
vector<vector<int>> compBiconexe;
stack<int> st;
int timer = 1;
int ans = 0;
void Articulation_Points(int node, int parent) {
isVisited[node] = true;
tin[node] = low[node] = timer++;
st.push(node);
for(auto neighbor : graph[node]) {
if(neighbor == parent)
continue;
if(!isVisited[neighbor]) {
Articulation_Points(neighbor, node);
low[node] = min(low[node], low[neighbor]);
if(low[neighbor] >= tin[node]) {
ans++;
vector<int> noduri;
while(!st.empty() && st.top() != node) {
int x = st.top();
noduri.push_back(x);
st.pop();
}
noduri.push_back(node);
compBiconexe.push_back(noduri);
}
}
else {
low[node] = min(low[node], tin[neighbor]);
}
}
}
int main() {
fin >> N >> M;
for(int i=1; i<=M; i++) {
int x,y;
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
Articulation_Points(1, 0);
fout << ans << "\n";
for(auto vec : compBiconexe) {
for(auto e : vec) {
fout << e << ' ';
}
fout << "\n";
}
return 0;
}