Pagini recente » Cod sursa (job #1300703) | Cod sursa (job #2463974) | Cod sursa (job #1886694) | Cod sursa (job #1803174) | Cod sursa (job #925455)
Cod sursa(job #925455)
#include <iostream>
#include <fstream>
using namespace std;
#define MAX_N 100000
ofstream fout("biconex.out");
struct nod
{
int nr,nr2;
nod *next;
}*First[MAX_N+5],*List[MAX_N+5],*Stack;
int N,M,NRC;
int Niv[MAX_N],NivMin[MAX_N];
void Insert(int x,int y,nod *p[MAX_N])
{
nod *q=new nod;
q->nr=y;
q->next=p[x];
p[x]=q;
}
void Read()
{
ifstream fin("biconex.in");
fin>>N>>M;
int i,x,y;
for(i=1;i<=M;i++)
{
fin>>x>>y;
Insert(x,y,First);
Insert(y,x,First);
}
fin.close();
}
void PutInStack(int nr,int nr2)
{
nod *q=new nod;
q->nr=nr;
q->nr2=nr2;
q->next=Stack;
Stack=q;
}
void AddComp(int k)
{
int nr,nr2;
nod *q;
NRC++;
for(q=Stack;q;)
{
nr=q->nr;
nr2=q->nr2;
Stack=Stack->next;
delete q;
q=Stack;
Insert(NRC,nr2,List);
if(nr==k)
break;
}
Insert(NRC,nr,List);
}
void WriteComp(nod *p)
{
if(p)
{
fout<<p->nr<<" ";
WriteComp(p->next);
}
else
fout<<'\n';
}
void Write()
{
int i;
fout<<NRC<<'\n';
for(i=1;i<=NRC;i++)
{
WriteComp(List[i]);
}
}
void DF(int k,int t,int niv)
{
Niv[k]=NivMin[k]=niv;
nod *q;
int cur;
for(q=First[k];q;q=q->next)
{
cur=q->nr;
if(cur==t)
continue;
if(Niv[cur]==0)
{
PutInStack(k,cur);
DF(cur,k,niv+1);
if(Niv[k]<=NivMin[cur])
{
AddComp(k);
}
if(NivMin[k]>NivMin[cur])
NivMin[k]=NivMin[cur];
}
else
if(NivMin[k]>Niv[cur])
NivMin[k]=Niv[cur];
}
}
int main()
{
Read();
DF(1,0,1);
Write();
return 0;
}