Pagini recente » Cod sursa (job #1781430) | Cod sursa (job #2200512) | Cod sursa (job #506598) | Cod sursa (job #2407514) | Cod sursa (job #402584)
Cod sursa(job #402584)
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <set>
#define N 100005
#define M 200005
using namespace std;
vector<int> L[N];
stack< pair<int, int > > S;
set<int> rez[M];
int tata[N],E[N],jos[N],niv[N],ind[M];
int kont=0,crit=0;
void dfs(int nod)
{
E[nod]=1;
int MIN=niv[nod]; //nivelul lui
for (vector<int>::iterator it=L[nod].begin(); it!=L[nod].end(); it++)
{
if (!E[*it])
{
tata[*it]=nod;
niv[*it]=niv[nod]+1;
dfs(*it);
//minimul valorilor fiilor lui
if (jos[*it]<MIN)
MIN=jos[*it];
}
//muchia de intoarcere
if (E[*it] && niv[*it]<niv[nod] && tata[nod]!=*it && niv[*it]<MIN)
MIN=niv[*it];
}
jos[nod]=MIN;
}
void biconex(int nod)
{
E[nod]=1;
for (vector<int>::iterator it=L[nod].begin(); it!=L[nod].end(); it++)
if (tata[nod]!=*it)
{
//muchia de intoarcere
if (E[*it] && niv[*it]<niv[nod]) S.push(make_pair(nod,*it));
if (!E[*it])
{
S.push(make_pair(nod,*it));
biconex(*it);
//a gasit un nod critic - scoate din stiva
if ((jos[*it]>=niv[nod] && nod!=1) || (nod==1 && crit))
{
kont++;
for (; S.top().first!=nod || S.top().second!=*it; S.pop())
{
rez[kont].insert(S.top().first);
rez[kont].insert(S.top().second);
}
rez[kont].insert(S.top().first);
rez[kont].insert(S.top().second);
S.pop();
}
}
}
}
int main()
{
int n,m;
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
L[x].push_back(y);
L[y].push_back(x);
}
niv[1]=1;
jos[1]=1;
dfs(1);
//se uita daca radacina e nod critic
int root=0;
for (vector<int>::iterator it=L[1].begin(); it!=L[1].end(); it++)
if (tata[*it]==1) root++;
if (root>1) crit=1;
memset(E,0,sizeof(E));
biconex(1);
if (!S.empty())
{
kont++;
for (; !S.empty(); S.pop())
{
rez[kont].insert(S.top().first);
rez[kont].insert(S.top().second);
}
}
printf("%d\n",kont);
for (int i=1; i<=kont; i++, printf("\n"))
for (set<int>::iterator it=rez[i].begin(); it!=rez[i].end(); it++)
printf("%d ",*it);
return 0;
}