Pagini recente » Cod sursa (job #2716727) | Cod sursa (job #1364615) | Cod sursa (job #1503392) | Cod sursa (job #1721458) | Cod sursa (job #1967834)
#include<cstdio>
#include<vector>
using namespace std;
const int NMAX = 100000;
int n,m;
vector<int> adj[1 + NMAX];
vector<int> vertex[1 + NMAX];
int vertex_used[1 + 2 * NMAX];
int level[1 + NMAX];
int level_min[1 + NMAX];
struct str
{
int l,r;
} stk[1 + 3 * NMAX];
int top;
vector<int> res[1 + NMAX];
int res_ct;
int mi(int a, int b)
{
if(a < b)
{
return a;
}
return b;
}
void solve(int node, int lvl)
{
level[node] = lvl;
level_min[node] = lvl;
vector<int>::iterator it = adj[node].begin();
vector<int>::iterator it2 = vertex[node].begin();
while(it != adj[node].end())
{
if(vertex_used[*it2] == 0)
{
vertex_used[*it2] = 1;
/*printf("* %d %d %d\n",node, level[node], level_min[node]);
for(int i = 1; i <= top; i++)
{
printf("%d %d\n", stk[i].l, stk[i].r);
}
printf("\n");*/
if(level[*it] == 0)
{
top++;
stk[top].l = node;
stk[top].r = *it;
solve(*it, lvl + 1);
}
level_min[node] = min(level_min[node], level_min[*it]);
if(level[node] <= level_min[*it])
{
res_ct++;
do
{
res[res_ct].push_back(stk[top].r);
if(stk[top].l == node && stk[top].r == *it)
{
res[res_ct].push_back(stk[top].l);
top--;
break;
}
top--;
} while(1);
}
}
it++;
it2++;
}
/*printf("%d %d %d\n",node, level[node], level_min[node]);
printf("\n");*/
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i++)
{
level_min[i] = 1000000000;
}
int x,y;
for(int i = 1; i <= m; i++)
{
scanf("%d %d", &x, &y);
adj[x].push_back(y);
adj[y].push_back(x);
vertex[x].push_back(i);
vertex[y].push_back(i);
}
solve(1, 1);
/*for(int i = 1; i <= n; i++)
{
printf("%d %d %d\n", i, level[i], level_min[i]);
}
printf("\n");*/
printf("%d\n",res_ct);
for(int i = 1; i <= res_ct; i++)
{
for(vector<int>::iterator it = res[i].begin(); it != res[i].end(); it++)
{
printf("%d ", *it);
}
printf("\n");
}
}