Pagini recente » Cod sursa (job #2237486) | Cod sursa (job #746615) | Cod sursa (job #1057466) | Cod sursa (job #904656) | Cod sursa (job #937137)
Cod sursa(job #937137)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int NMAX = 100005;
int n,m,x,y,i,j,cnt,N;
int Dft[NMAX]; // Dft[x] = numarul de ordine al nodului x dupa parcurgerea DFS
int Low[NMAX]; // Low[x] = numarul de ordine al primului nod ce poate fi atins din x pe alt drum decat cel din parcurgerea DFS
vector<int> V[NMAX],Sol[NMAX];
vector<pair<int,int> > St;
void Get_Sol(int A,int B)
{
int X,Y;
vector<pair<int,int> >::iterator it; N++;
do
{
it=St.end(); it--;
X=it->first;
Y=it->second;
St.pop_back();
Sol[N].push_back(Y);
}
while(X!=A || Y!=B);
Sol[N].push_back(X);
}
void DFS(int Node,int Father)
{
Dft[Node]=Low[Node]=++cnt;
for(vector<int>::iterator it=V[Node].begin();it!=V[Node].end();it++)
{
if(*it==Father) continue;
if(!Dft[*it])
{
St.push_back(make_pair(Node,*it));
DFS(*it,Node);
Low[Node]=min(Low[Node],Low[*it]);
// actualizam Low pe baza fiilor
if(Low[*it]>=Dft[Node]) Get_Sol(Node,*it);
// am gasit un punct de articulatie
}
else Low[Node]=min(Low[Node],Dft[*it]);
// am gasit o muchie de intoarcere si putem sa actualizam actualizam Low
}
}
void Read()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(;m;m--)
{
scanf("%d%d",&x,&y);
V[x].push_back(y);
V[y].push_back(x);
}
DFS(1,0);
}
void Print()
{
printf("%d\n",N);
for(i=1;i<=N;i++)
{
for(vector<int>::iterator it=Sol[i].begin();it!=Sol[i].end();it++) printf ("%d ",*it);
printf("\n");
}
}
int main()
{
Read();
Print();
return 0;
}