Pagini recente » Cod sursa (job #714992) | Cod sursa (job #1176839) | Cod sursa (job #2870823) | Cod sursa (job #2758821) | Cod sursa (job #1097767)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define pb push_back
#define dmax 1234
#define x first
#define y second
int n, m, dfn[dmax], l[dmax], nr, c, start, nrs, con[dmax];
vector <int > v[dmax];
typedef pair <int, int> dp;
vector <dp> st;
vector <int > v2[dmax];
void print_biconex(int a, int b)
{
c++;
dp as=make_pair(a, b);
dp is=make_pair(b, a);
for(int i=st.size()-1;i>=0;i--)
{
if(con[st[i].x]!=c)
{
con[st[i].x]=c;
v2[c].pb(st[i].x);
}
if(con[st[i].y]!=c)
{
con[st[i].y]=c;
v2[c].pb(st[i].y);
}
st.pop_back();
if(as==st[i] || is==st[i])
break;
}
}
void DFS(int k, int kk)
{
nr++;
dfn[k]=nr;
l[k]=nr;
for(int i=0; i<v[k].size(); i++)
{
int a=v[k][i];
if(a!=kk && dfn[a]<dfn[k])
{
dp asd;
asd.x=a;
asd.y=k;
st.pb(asd);
}
if(dfn[a]==0)
{
DFS(a, k);
l[k]=min(l[a], l[k]);
if(l[a]>=dfn[k]) {
//printf("muchia: %i %i cu bic:", k, a);
print_biconex(k, a);
}
}
else
{
if(a!=kk)
l[k]=min(l[k], dfn[a]);
}
}
}
void read()
{
int a, b;
scanf("%i%i", &n, &m);
for(int i=1; i<=m; i++)
{
scanf("%i%i", &a, &b);
{
v[a].pb(b);
v[b].pb(a);
}
}
}
int main()
{
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
read();
start=1;
DFS(start, -1);
//print_biconex(1,2);
printf("%i\n", c);
for(int i=1;i<=c;i++)
{
for(int j=0;j<v2[i].size();j++)
printf("%i ", v2[i][j]);
printf("\n");
}
return 0;
}