Pagini recente » Cod sursa (job #452845) | Cod sursa (job #2234132) | Cod sursa (job #2472742) | Cod sursa (job #2187282) | Cod sursa (job #2668448)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N,M,x,y,i,j,nrb, vizitat[100001], stiva[100001],varf,niv[100001],minim[100001];
vector<int> adj[100001], biconexe[100001];
void DFS(int nod, int parinte)
{
vizitat[nod]=1;
minim[nod]= niv[nod];
stiva[++varf]=nod;
for (auto nodcurent : adj[nod])
{
if (nodcurent==parinte) continue;
if (vizitat[nodcurent])
{
minim[nod] = min(minim[nod], niv[nodcurent]);}
else
{
niv[nodcurent]=niv[nod]+1;
DFS(nodcurent, nod);
if (minim[nodcurent]>=niv[nod])
{
nrb++;
while (varf && stiva[varf]!=nodcurent)
biconexe[nrb].push_back(stiva[varf--]);
biconexe[nrb].push_back(stiva[varf--]);
biconexe[nrb].push_back(nod);
}
minim[nod]=min(minim[nod], minim[nodcurent]);
}
}
}
int main()
{
f>>N>>M;
for (i=1; i<=M; i++)
{
f>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
DFS(1,0);
g<<nrb<<endl;
for (i=1; i<=nrb; i++)
{
for (auto j:biconexe[i])
g<<j<<" ";
g<<endl;}
f.close();
g.close();
}