Pagini recente » Cod sursa (job #1950061) | Cod sursa (job #1080729) | Cod sursa (job #1479103) | Cod sursa (job #765571) | Cod sursa (job #2926256)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int const N = 1e5 + 3;
int n , m , a , b;
int idx[N] , low[N];
vector<int> v[N];
vector<vector<int> > comp;
stack<pair<int , int> > st;
void dfs(int x , int t){
idx[x] = low[x] = ++idx[0];
int fii(0);
for(int& y : v[x]){
if(y == t) continue;
if(!idx[y]){
++fii;
st.emplace(x , y);
dfs(y , x);
low[x] = min(low[x] , low[y]);
if((x == 1 && fii > 1) || (x != 1 && low[y] >= idx[x])){
vector<int> c;
while(!(st.top().first == x && st.top().second == y)){
c.push_back(st.top().first) , c.push_back(st.top().second);
st.pop();
}
c.push_back(x) , c.push_back(y);
st.pop();
comp.push_back(c);
}
}else{
low[x] = min(low[x] , idx[y]);
if(idx[y] < idx[x])
st.emplace(x , y);
}
}
}
int main()
{
fin >> n >> m;
for(int i = 1 ; i <= m ; ++ i){
fin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for(int i = 1 ; i <= n ; ++ i){
if(idx[i]) continue;
dfs(i , 0);
if(!st.empty()){
vector<int> c;
while(!st.empty()){
c.push_back(st.top().first) , c.push_back(st.top().second);
st.pop();
}
comp.push_back(c);
}
}
fout << comp.size() << '\n';
for(auto& x : comp){
sort(x.begin() , x.end());
auto last = unique(x.begin() , x.end());
x.erase(last , x.end());
for(int& y : x)
fout << y << ' ';
fout << '\n';
}
return 0;
}