Cod sursa(job #2285710)

Utilizator Monstergentleman35Ciopraga Razvan Monstergentleman35 Data 18 noiembrie 2018 23:18:48
Problema Componente biconexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.43 kb
#include <bits/stdc++.h>
#include <vector>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

struct Elem
{
 int val;
 Elem *next;
};

struct Item
{
 Elem *st,*cur;
};

struct Mem
{
 int ax,bx;
 Mem *bak;
};

vector <Item> Grupe;
int n,m,a,b,nrgrupe,nrramuri;
int i,cand;
Elem *leg,*parc2;
Item Adiac[100005];
int low[100005];
int dfn[100005];
Mem *sf,*ad,*sters;
Item hol;

void dfs(int,int);
void extractcomp(int,int);

int main()
{
 fin>>n>>m;
 hol.st=0;
 hol.cur=0;
 Grupe.push_back(hol);
 for (i=1;i<=n;i++)
 {
  Adiac[i].st=new Elem;
  Adiac[i].st->val=0;
  Adiac[i].st->next=0;
  Adiac[i].cur=Adiac[i].st;
 }
 sf=new Mem;
 sf->bak=0;
 while (m)
 {
  m--;
  fin>>a>>b;
  leg=new Elem;
  leg->val=b;
  leg->next=0;
  Adiac[a].cur->next=leg;
  Adiac[a].cur=leg;
  leg=new Elem;
  leg->val=a;
  leg->next=0;
  Adiac[b].cur->next=leg;
  Adiac[b].cur=leg;
 }
 dfs(1,0);
 fout<<nrgrupe<<"\n";
 for (i=1;i<=nrgrupe;i++)
 {
  parc2=Grupe.at(i).st->next;
  while (parc2!=0)
  {
   fout<<parc2->val<<" ";
   parc2=parc2->next;
  }
  fout<<"\n";
 }
 return 0;
}

void dfs(int x,int tx)
{
 Elem *i2;
 int y;
 cand++;
 dfn[x]=low[x]=cand;
 i2=Adiac[x].st->next;
 while (i2!=NULL)
 {
  y=i2->val;
  if (dfn[y]==0)
  {
   if (x==1)
    nrramuri++;
   ad=new Mem;
   ad->bak=sf;
   ad->ax=y;
   ad->bx=x;
   sf=ad;
   dfs(y,x);
   low[x]=min(low[y],low[x]);
   if (low[y]>=dfn[x])
    extractcomp(y,x);
  }
  else
  {
   if (y!=tx&&dfn[y]<dfn[x])
   {
    ad=new Mem;
    ad->bak=sf;
    ad->ax=y;
    ad->bx=x;
    sf=ad;
    low[x]=min(low[x],low[y]);
   }
  }
  i2=i2->next;
 }
}

void extractcomp(int x,int tx)
{
 bool Select[100005];
 int i2,a2,b2;
 Item holder;
 for (i2=1;i2<=100000;i2++)
  Select[i2]=0;
 nrgrupe++;
 holder.st=new Elem;
 holder.st->next=0;
 holder.st->val=0;
 holder.cur=holder.st;
 Grupe.push_back(holder);
 Mem *parc;
 parc=sf;
 do
 {
  sters=parc;
  a2=parc->ax;
  b2=parc->bx;
  if (Select[a2]==0)
  {
   Select[a2]=1;
   leg=new Elem;
   leg->val=a2;
   leg->next=0;
   Grupe.at(nrgrupe).cur->next=leg;
   Grupe.at(nrgrupe).cur=leg;
  }
  if (Select[b2]==0)
  {
   Select[b2]=1;
   leg=new Elem;
   leg->val=b2;
   leg->next=0;
   Grupe.at(nrgrupe).cur->next=leg;
   Grupe.at(nrgrupe).cur=leg;
  }
  sf=parc->bak;
  parc=parc->bak;
  delete sters;
 } while (a2!=x||b2!=tx);
}