Pagini recente » Cod sursa (job #3255666) | Cod sursa (job #720674) | Cod sursa (job #2417792) | Cod sursa (job #824921) | Cod sursa (job #2952513)
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int const N = 1e5 + 3;
int n , m , timp , biconexe;
int tin[N] , low[N] , viz[N];
vector<int> v[N];
vector<pair<int , int> > bcx_m[N];
vector<int> bcx[N];
stack<pair<int , int> > st;
void dfs(int x , int p = -1){
viz[x] = 1;
tin[x] = low[x] = ++timp;
int fii(0);
for(int y : v[x]){
if(y == p) continue;
if(viz[y]){
low[x] = min(low[x] , tin[y]);
if(tin[y] < tin[x]){
st.emplace(x , y);
}
}else{
++ fii;
st.emplace(x , y);
dfs(y , x);
low[x] = min(low[x] , low[y]);
if(p != -1 && low[y] >= tin[x]){
++ biconexe;
int a , b;
do{
a = st.top().fi , b = st.top().se;
bcx_m[biconexe].push_back(st.top());
st.pop();
}while(!(a == x && b == y));
}
}
}
if(p == -1 && fii > 1){
++ biconexe;
int a , b;
do{
a = st.top().fi , b = st.top().se;
bcx_m[biconexe].push_back(st.top());
st.pop();
}while(a != x);
}
}
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(!viz[i]){
dfs(i);
if(!st.empty()){
++ biconexe;
while(!st.empty()){
bcx_m[biconexe].push_back(st.top());
st.pop();
}
}
}
}
for(int i = 1 ; i <= biconexe ; ++ i){
vector<int> bcn;
for(auto y : bcx_m[i]){
bcn.push_back(y.fi);
bcn.push_back(y.se);
}
sort(bcn.begin() , bcn.end());
bcn.erase(unique(bcn.begin() , bcn.end()) , bcn.end());
bcx[i] = bcn;
}
fout << biconexe << '\n';
for(int i = 1 ; i <= biconexe ; ++ i){
for(int y : bcx[i])
fout << y << ' ';
fout << '\n';
}
return 0;
}