Pagini recente » Cod sursa (job #2220220) | Cod sursa (job #1082854) | Cod sursa (job #1292765) | Cod sursa (job #2034292) | Cod sursa (job #3192356)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int nMax=(int)1e5+5;
int op, n, m, x, y, dfn[nMax], low[nMax], nrCompBi;
vector<int> g[nMax];
vector<vector<int>> muchii;
stack<pair<int, int>> s;
void afis(int nod, int k)
{
nrCompBi++;
int auxFirst, auxSecond;
vector<int> aux;
do {
auxFirst=s.top().first, auxSecond=s.top().second;
s.pop();
aux.push_back(auxFirst);
aux.push_back(auxSecond);
}
while(auxFirst != nod || auxSecond != k);
muchii.push_back(aux);
}
void biconex(int nod, int tata, int nr)
{
dfn[nod]=low[nod]=nr;
for(auto k: g[nod])
{
if(k == tata)
continue;
if(dfn[k] == -1)
{
s.push({nod, k});
biconex(k, nod, nr + 1);
low[nod]=min(low[nod], low[k]);
if(low[k] >= dfn[nod])
afis(nod, k);
}
else low[nod]=min(low[nod], dfn[k]);
}
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fin>>n>>m;
for(int i=0; i<m; i++)
{
fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1; i<=n; i++)
dfn[i]=low[i]=-1;
biconex(1, 0, 0);
fout<<nrCompBi<<'\n'; //muchii.size()
for(int i=0; i<muchii.size(); i++)
{
sort(muchii[i].begin(), muchii[i].end());
muchii[i].erase(unique(muchii[i].begin(), muchii[i].end()), muchii[i].end());
for(int j=0; j<muchii[i].size(); j++)
fout<<muchii[i][j]<<' ';
fout<<'\n';
}
fin.close(); fout.close();
return 0;
}