Pagini recente » Cod sursa (job #2241081) | Cod sursa (job #309785) | Cod sursa (job #1407694) | Cod sursa (job #1960911) | Cod sursa (job #1412650)
#include<cstdio>
#include<vector>
#include<set>
#include<stack>
#define NMAX 100001
#define min(a,b) (a>b?b:a)
using namespace std;
struct per
{
int l,r;
};
int n,m,cbc;
int viz[NMAX],low[NMAX];
set<int>s[NMAX];
vector<int>v[NMAX];
stack<per>st;
per pereche(int x,int y)
{
per X; X.l=x; X.r=y;
return X;
}
void DFS(int nod,int niv,int tata)
{
low[nod]=niv;
viz[nod]=1;
for(int i = 0; i < v[nod].size(); ++i)
{
int fiu = v[nod][i];
if (fiu == tata) continue;
if (viz[fiu] ==0)
{
st.push(pereche(nod,fiu));
DFS(fiu,niv+1,nod);
low[nod] = min(low[nod],low[fiu]);
if (low[fiu] >= niv)
{
++cbc;
per X;
do
{
X = st.top();
st.pop();
s[cbc].insert(X.l);
s[cbc].insert(X.r);
}while(X.l != nod || X.r != fiu);
}
}
else low[nod] = min(low[nod],low[fiu]);
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
int x,y;
for(int i = 1; i <= m; ++i)
{
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
for(int i = 1; i <= n; ++i)
{
if (viz[i] == 0)
{
DFS(i,1,0);
}
}
printf("%d\n",cbc);
for(int i = 1; i <= cbc; ++i)
{
set<int>::iterator it;
for(it = s[i].begin(); it != s[i].end(); ++it)
printf("%d ",*it);
printf("\n");
}
return 0;
}