Pagini recente » Cod sursa (job #504526) | Cod sursa (job #1391486)
#include <fstream>
#include <vector>
#include <stack>
#include <set>
#define NMAX 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct muchie
{ int x, y;
};
vector<int> G[NMAX];
stack<muchie> St;
set<int> sol[NMAX];
set<int>::iterator it;
int n, m, i, j, nr, U[NMAX], T[NMAX], niv[NMAX], L[NMAX];
void DF(int nod)
{ U[nod]=1;
L[nod]=niv[nod];
vector<int>::iterator it;
for (it=G[nod].begin(); it!=G[nod].end(); ++it)
if (*it!=T[nod])
{ if (!U[*it])
{ muchie a;
a.x=nod;
a.y=*it;
St.push(a);
niv[*it]=1+niv[nod];
T[*it]=nod;
DF(*it);
L[nod]=min(L[nod], L[*it]);
if (L[*it]>=niv[nod])
{ ++nr;
int i, j;
while (i!=nod || j!=*it)
{ i=St.top().x;
j=St.top().y;
St.pop();
sol[nr].insert(i);
sol[nr].insert(j);
}
}
}
else
L[nod]=min(L[nod], niv[*it]);
}
}
int main()
{ f>>n>>m;
for (; m; --m)
{ f>>i>>j;
G[i].push_back(j);
G[j].push_back(i);
}
niv[1]=1;
DF(1);
g<<nr<<'\n';
for (i=1; i<=nr; ++i)
{ for (it=sol[i].begin(); it!=sol[i].end(); ++it)
g<<*it<<' ';
g<<'\n';
}
return 0;
}