Pagini recente » Cod sursa (job #3201272) | Cod sursa (job #1861896) | Cod sursa (job #521908) | Cod sursa (job #671510) | Cod sursa (job #1413277)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int N, M, nrsol;
int nodLvl[100005], nodInt[100005];
vector<int> V[100005], sol[100005];
stack<pair<int, int> > ST;
bool used[100005];
void make_sol(int nod, int fiu)
{
while (!ST.empty() && (ST.top().first != nod || ST.top().second != fiu))
{
sol[nrsol].push_back(ST.top().second);
ST.pop();
}
ST.pop();
sol[nrsol].push_back(fiu);
sol[nrsol].push_back(nod);
}
void dfs(int nod, int TT, int lvl)
{
nodLvl[nod] = lvl;
for (vector<int>::iterator it = V[nod].begin(); it != V[nod].end(); ++it)
{
int vecin = *it;
if (*it == TT)
continue;
if (!used[*it])
{
used[*it] = true;
ST.push(make_pair(nod, *it));
dfs(*it, nod, lvl + 1);
if (nodLvl[nodInt[nod]] > nodLvl[nodInt[*it]])
nodInt[nod] = nodInt[*it];
if (nodLvl[nodInt[*it]] >= lvl)
{
++nrsol;
make_sol(nod, *it);
}
}
else if (used[*it])
{
if (nodLvl[nodInt[nod]] > nodLvl[nodInt[*it]])
nodInt[nod] = nodInt[*it];
}
}
}
int main()
{
fin >> N >> M;
for (int i = 1, nod1, nod2; i <= M; ++i)
{
fin >> nod1 >> nod2;
V[nod1].push_back(nod2);
V[nod2].push_back(nod1);
}
for (int i = 1; i <= N; ++i)
nodInt[i] = i;
used[1] = true;
dfs(1, 1, 1);
fout << nrsol << '\n';
for (int i = 1; i <= nrsol; ++i)
{
for (vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
fout << *it << ' ';
fout << '\n';
}
fin.close();
fout.close();
return 0;
}