Pagini recente » Cod sursa (job #2577159) | Cod sursa (job #1468387) | Clasament simulare_oji_adi | Cod sursa (job #2917428) | Cod sursa (job #2926254)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int const N = 1e5 + 3;
int n , m;
int low[N] , d[N] , idx[N];
stack<pair<int , int> > st;
vector<vector<int> > comp;
vector<int> v[N];
void dfs(int x , int t , int de){
idx[x] = low[x] = ++idx[0];
d[x] = de;
int fii(0);
for(int& y : v[x]){
if(y == t) continue;
if(!idx[y]){
st.emplace(x , y);
++fii;
dfs(y , x , de + 1);
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){
int a , b;
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 , 0);
if(st.size()){
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& S : comp){
sort(S.begin() , S.end());
auto x = unique(S.begin() , S.end());
S.erase(x , S.end());
for(auto& x : S)
fout << x << ' ';
fout << '\n';
}
return 0;
}