Pagini recente » Cod sursa (job #2311798) | Cod sursa (job #3259358) | Cod sursa (job #480330) | Cod sursa (job #9661) | Cod sursa (job #2721396)
#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 100000
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, vf, nrcb, nivel[NMAX+10], lowpoint[NMAX+10], viz[NMAX+10], stiva[NMAX+10];
vector <int> nod[NMAX+10], cb[NMAX+10];
void dfs(int x, int p)
{ nivel[x] = nivel[p] + 1;
viz[x] = 1;
lowpoint[x] = nivel[x];
stiva[++vf] = x;
for(auto u : nod[x])
{ if(u == p) continue;
if(!viz[u])
{ dfs(u, x);
if(lowpoint[u] >= nivel[x])
{ nrcb++;
while(stiva[vf] != u)
{ cb[nrcb].push_back(stiva[vf]);
vf--;
}
cb[nrcb].push_back(u);
cb[nrcb].push_back(x);
vf--;
}
lowpoint[x] = min(lowpoint[x], lowpoint[u]);
}
else
lowpoint[x] = min(lowpoint[x], nivel[u]);
}
}
int main()
{
fin >> n >> m;
for(int i=1; i<=m; i++)
{ int nod1, nod2;
fin >> nod1 >> nod2;
nod[nod1].push_back(nod2);
nod[nod2].push_back(nod1);
}
for(int i=1; i<=n; i++)
if(!viz[i])
dfs(i, 0);
fout << nrcb << '\n';
for(int i=1; i<=nrcb; i++)
{ for(auto u : cb[i])
fout << u << ' ';
fout << '\n';
}
return 0;
}