Pagini recente » Cod sursa (job #673557) | Cod sursa (job #2435676) | Cod sursa (job #1322838) | Cod sursa (job #2919330) | Cod sursa (job #1376552)
#include <fstream>
#include <stack>
#define N 100001
#define M 200001
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n, m;
int t[N], l[N], niv[N];
bool ok[N];
int lst[N], vf[2 * M], vf2[2 * M], urm[2 * M], nvf = 0;
stack<int> s;
int rez[M + 2 * N], nrez = 0;
int cbicnx = 0;
void df(int x)
{
ok[x] = 1;
l[x] = niv[x];
for(int i = lst[x]; i; i = urm[i])
{
int y = vf[i];
if(!ok[y])
{
t[y] = x;
niv[y] = niv[x] + 1;
s.push(i);
df(y);
if(l[y] < l[x])
l[x] = l[y];
if(l[y] >= niv[x])
{
cbicnx++;
int j;
do
{
j = s.top();
s.pop();
rez[++nrez] = vf[j];
}while(j != i);
rez[++nrez] = vf2[i];
rez[++nrez] = -1;
}
}
else if(y != t[x] && niv[y] < l[x])
l[x] = niv[y];
}
}
int main()
{
in >> n >> m;
for(int i = 1; i <= m; i++)
{
int x, y;
in >> x >> y;
vf[++nvf] = y;
vf2[nvf] = x;
urm[nvf] = lst[x];
lst[x] = nvf;
vf[++nvf] = x;
vf2[nvf] = y;
urm[nvf] = lst[y];
lst[y] = nvf;
}
for(int i = 1; i <= n; i++)
if(!ok[i])
{
niv[i] = 1;
df(i);
}
out << cbicnx << '\n';
for(int i = 1; i <= nrez; i++)
if(rez[i] != -1)
out << rez[i] << ' ';
else
out << '\n';
return 0;
}