Pagini recente » Cod sursa (job #2285418) | Cod sursa (job #484578) | Cod sursa (job #173773) | Cod sursa (job #1755968) | Cod sursa (job #2850599)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 100001;
vector <int> Ad[NMAX], biconex[NMAX];
stack <int> S;
int n,m,nrc;
int desc[NMAX], low[NMAX];
bool vis[NMAX];
void DFS(int nod, int parent)
{
vis[nod] = 1;
S.push(nod);
desc[nod] = desc[parent] + 1;
low[nod] = desc[nod];
for (int i = 0; i < Ad[nod].size(); ++i)
{
int w = Ad[nod][i];
if (vis[w] == 0)
{
DFS(w,nod);
low[nod] = min (low[nod], low[w]);
if (low[w] >= desc[nod] && w != parent)
{
nrc++;
S.push(nod);
while ( !S.empty() && S.top() != w)
{
biconex[nrc].push_back(S.top());
S.pop();
}
if (!S.empty())
{
biconex[nrc].push_back(S.top());
S.pop();
}
}
}
else if (w != parent)
{
low[nod] = min (low[nod], desc[w]);
}
}
}
int main()
{
fin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int x,y;
fin >> x >> y;
Ad[x].push_back(y);
Ad[y].push_back(x);
}
DFS(1,0);
fout << nrc << '\n';
for (int i = 1; i <= nrc; ++i)
{
for (int j = 0; j < biconex[i].size(); ++j)
fout << biconex[i][j] << ' ';
fout << '\n';
}
return 0;
}