Pagini recente » Cod sursa (job #164321) | Cod sursa (job #280813) | Cod sursa (job #1021993) | Cod sursa (job #2538590) | Cod sursa (job #2978227)
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
#define fi first
#define se second
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int const N = 2e5 + 3;
typedef pair<int,int> pii;
int n , m , biconexe;
int idx[N] , low[N];
stack<pii> st;
vector<int> v[N];
vector<int> bcx[N];
void dfs(int x , int t = -1){
idx[x] = ++idx[0];
low[x] = idx[x];
int fii(0);
for(int y : v[x]){
if(y == t)
continue;
if(idx[y]){
low[x] = min(low[x] , idx[y]);
if(idx[x] >= idx[y])
st.emplace(x , y);
continue;
}
++fii;
st.emplace(x , y);
dfs(y , x);
if((t == -1 && fii > 1) || (t != -1 && low[y] >= idx[x])){
++biconexe;
int a , b;
do{
a = st.top().fi;
b = st.top().se;
st.pop();
bcx[biconexe].push_back(a);
bcx[biconexe].push_back(b);
}while(a != x || b != 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);
if(st.empty())
continue;/*
++biconexe;
while(!st.empty()){
bcx[biconexe].push_back(st.top().fi);
bcx[biconexe].push_back(st.top().se);
st.pop();
}*/
}
fout << biconexe << '\n';
for(int i = 1 ; i <= biconexe ; ++ i){
sort(bcx[i].begin() , bcx[i].end());
bcx[i].erase(unique(bcx[i].begin() , bcx[i].end()) , bcx[i].end());
for(int j : bcx[i])
fout << j << ' ';
fout << '\n';
}
return 0;
}