Pagini recente » Clasamentul arhivei de probleme | Cod sursa (job #2654915) | Cod sursa (job #3252908) | Cod sursa (job #1398674) | Cod sursa (job #2677734)
#include <fstream>
#include <vector>
#define K 100002
using namespace std;
ifstream fin("biconexe.in");
ofstream fout("biconexe.out");
int t,n,m,i,x,y,f[K],low[K],niv[K],cbc;
vector <int> v[K],stiva,C[K];
void dfs(int nod,int tata,int nivel){
f[nod]=1;
low[nod]=niv[nod]=nivel;
stiva.push_back(nod);
for(auto vecin : v[nod]){
if(vecin==tata)continue;
if(f[vecin]){
low[nod]=min(low[nod],niv[vecin]);
continue;
}
dfs(vecin,nod,nivel+1);
low[nod]=min(low[nod],low[vecin]);
if(low[vecin]>=niv[nod]){ ///detectez comp biconexa
cbc++;
int x=0;
while(x!=vecin){
x=stiva.back();
stiva.pop_back();
C[cbc].push_back(x);
}
C[cbc].push_back(nod);
}
}
}
int main(){
fin>>n>>m;
for(i=1;i<=m;i++){
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0,1);
fout<<cbc<<"\n";
for(i=1;i<=cbc;i++){
for(auto x: C[i])
fout<<x<<" ";
fout<<"\n";
}
return 0;
}