Pagini recente » Cod sursa (job #1648113) | Cod sursa (job #1417265) | Cod sursa (job #1428691) | Cod sursa (job #2166316) | Cod sursa (job #2907442)
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N,M,x,y,i,j,nrb, vizitat[nmax], stiva[nmax],varf,niv[nmax],minim[nmax];
vector<int> adj[nmax], biconexe[nmax];
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();
}