Pagini recente » Cod sursa (job #1129499) | Cod sursa (job #764896) | Cod sursa (job #2316649) | Cod sursa (job #735949) | Cod sursa (job #2814770)
#include <fstream>
#include <vector>
#include <stack>
std::ifstream in("biconex.in");
std::ofstream out("biconex.out");
const int N = 1e5+1;
int n, m, t[N], t_min[N], curr_time, curr_cbc;
std::vector<int> g[N], cbc[N];
std::stack<int> st;
/*const int N = 1e5+1;
int n, m, t[N], t_min[N], curr_time;
std::vector<int> g[N], p_art;
// puncte de articulatie
void dfs(int curr_node, int tata){
t_min[curr_node] = t[curr_node] = ++curr_time;
int nr_fii = 0;
for(auto fiu : g[curr_node]){
if(t[fiu] == 0){ //fiu nevizitat
++nr_fii;
dfs(fiu, curr_node);
t_min[curr_node] = std::min(t_min[curr_node], t_min[fiu]);
if(t_min[fiu] >= t[curr_node] && tata != 0){
p_art.push_back(curr_node); //curr_node -> este punct de articulatie
}
}
else if(fiu != tata){
t_min[curr_node] = std::min(t_min[curr_node], t[fiu]);
}
}
if(tata == 0 && nr_fii > 1){
p_art.push_back(curr_node);
}
}
*/
void add_cbc(int x, int y){
++curr_cbc;
while(st.top() != y){
cbc[curr_cbc].push_back(st.top());
st.pop();
}
cbc[curr_cbc].push_back(y);
st.pop();
cbc[curr_cbc].push_back(x);
}
void dfs(int curr_node, int tata){
t_min[curr_node] = t[curr_node] = ++curr_time;
st.push(curr_node);
for(auto fiu : g[curr_node]){
if(t[fiu] == 0){ //fiu nevizitat
dfs(fiu, curr_node);
t_min[curr_node] = std::min(t_min[curr_node], t_min[fiu]);
if(t_min[fiu] >= t[curr_node]){
add_cbc(curr_node, fiu);
}
}
else if(fiu != tata){
t_min[curr_node] = std::min(t_min[curr_node], t[fiu]);
}
}
}
int main(){
in>>n>>m;
for(int i=0;i<m;++i){
int a,b;
in>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
for(int i = 1; i <= n; ++i){
if(t[i] != 0) continue;
dfs(i, 0);
}
out<< curr_cbc << '\n';
for(int i = 1; i <= curr_cbc; ++i){
for(auto x : cbc[i])
out << x << ' ';
out << '\n';
}
in.close();
out.close();
return 0;
}