Pagini recente » Cod sursa (job #1646402) | Cod sursa (job #3129861) | Cod sursa (job #2122421) | Cod sursa (job #858490) | Cod sursa (job #2475834)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=1e5+4;
int n,m,id,cntCb;
int dfn[NMAX],low[NMAX];
stack <int> stk;
vector <int> g[NMAX];
vector <int> cb[NMAX];
void dfs(int node, int father){
dfn[node]=++id;
low[node]=dfn[node];
for(auto it:g[node]){
if(it!=father){
if(low[it])
low[node]=min(low[node], low[it]);
if(!dfn[it]){
dfs(it, node);
low[node]=min(low[node], low[it]);
if(low[it]>=dfn[node]){
//am gasit o componenta biconexa =)
while(!stk.empty()){
cb[cntCb].push_back(stk.top());
stk.pop();
}
cb[cntCb].push_back(node);
++cntCb;
}
}
}
}
stk.push(node);
}
int main(){
int x,y;
fin>>n>>m;
for(int i=0;i<m;++i){
fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,0);
fout<<cntCb<<'\n';
for(int i=0;i<cntCb;++i){
for(auto it:cb[i])
fout<<it<<' ';
fout<<'\n';
}
return 0;
}