Pagini recente » Cod sursa (job #1805242) | Cod sursa (job #2492524) | Cod sursa (job #2413870) | Cod sursa (job #1624259) | Cod sursa (job #3220183)
#include <fstream>
#include <climits>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout("biconex.out");
int n,m,p,i,x,y,k,nr,niv[100003],niv_min[100003],st[100003];
bool viz[100003];
vector <int> L[100003];
vector <int> comp_biconex[100003];
void dfs(int nod,int t)
{
viz[nod]=1;
niv[nod]=niv[t]+1;
niv_min[nod]=min(niv_min[nod],niv[nod]);
st[++nr]=nod;
for(auto j:L[nod])
{
if(j!=t)
{
int fiu=j;
if(!viz[fiu])
{
dfs(fiu,nod);
niv_min[nod]=min(niv_min[nod],niv_min[fiu]);
if(niv[nod]<=niv_min[fiu])///det componentelor biconexe
{
while(st[nr]!=fiu)///det componentelor biconexe
{
comp_biconex[k].push_back(st[nr]);
nr--;
}
comp_biconex[k].push_back(fiu);
nr--;
comp_biconex[k].push_back(nod);
k++;
}
}
else
niv_min[nod]=min(niv_min[nod],niv[fiu]);
}
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
for(int i=1;i<=n;i++)
niv_min[i]=2e9;
nr=0;
k=1;
niv[0]=0;
niv[1]=1;
niv_min[1]=1;
dfs(1,0);
fout<<k-1<<"\n";
for(int i=1;i<k;i++)
{
for(auto j:comp_biconex[i])
fout<<j<<" ";
fout<<"\n";
}
return 0;
}