Pagini recente » Cod sursa (job #3338550) | Cod sursa (job #3311916) | Cod sursa (job #3344042) | Cod sursa (job #3346682) | Cod sursa (job #3345053)
#include<iostream>
#include<fstream>
#include<stack>
#include<vector>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX=1e5;
int n,m,x,y,k;
stack<int>s;
vector<int>v[NMAX+5];
vector<vector<int>>compbiconexe;
int nvl[NMAX+5],nvlmin[NMAX+5];
void addcmp(int nod,int tata){
vector<int>comp={tata};
k=0;
do{
k=s.top();
comp.push_back(k);
s.pop();
}while(k!=nod);
compbiconexe.push_back(comp);
}
void dfs(int nod,int tata){
s.push(nod);
nvl[nod]=nvl[tata]+1;
nvlmin[nod]=nvl[nod];
for(auto f:v[nod]){
if(f==tata)continue;
if(nvl[f]==0){
dfs(f,nod);
if(nvlmin[f]>=nvl[nod])addcmp(f,nod);
nvlmin[nod]=min(nvlmin[nod],nvlmin[f]);
}
else{
nvlmin[nod]=min(nvlmin[nod],nvl[f]);
}
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++){
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
fout<<compbiconexe.size()<<'\n';
for(auto x:compbiconexe){
for(auto y:x)fout<<y<<' ';
fout<<'\n';
}
return 0;
}