Cod sursa(job #2265526)

Utilizator Monstergentleman35Ciopraga Razvan Monstergentleman35 Data 21 octombrie 2018 13:12:35
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.8 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Item
{
 long long val;
 Item *next;
};

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


int n,m,a,b,i,iaux;
ListaAd Adiac[100005],AdiacT[100005];
bool Viz[100005];
short int Mem[100005],Grupe[100005];
int nrmem,nrcomp,out;
Item *elem;

void dfs(int);
void dfs2(int);

int main()
{
 fin>>n>>m;
 for (i=1;i<=n;i++)
 {
  Adiac[i].st=new Item;
  Adiac[i].st->val=0;
  Adiac[i].cur=Adiac[i].st;
  AdiacT[i].st=new Item;
  AdiacT[i].st->val=0;
  AdiacT[i].cur=AdiacT[i].st;
 }
 Viz[0]=1;
 while (m!=0)
 {
  m--;
  fin>>a>>b;
  elem=new Item;
  elem->val=b;
  Adiac[a].cur->next=elem;
  Adiac[a].cur=elem;
  Adiac[a].cur->next=0;
  elem=new Item;
  elem->val=a;
  AdiacT[b].cur->next=elem;
  AdiacT[b].cur=elem;
  AdiacT[b].cur->next=0;
 }
 for (i=1;i<=n;i++)
  if (Viz[i]==0)
 {
  Viz[i]=1;
  dfs(i);
  nrmem++;
  Mem[nrmem]=i;
 }
 for (i=1;i<=n;i++)
  Adiac[i].st=AdiacT[i].st;
 for (i=1;i<=n;i++)
  Viz[i]=0;
 while (nrmem!=0)
 {
  if (Viz[Mem[nrmem]]==0)
  {
   nrcomp++;
   Grupe[Mem[nrmem]]=nrcomp;
   Viz[Mem[nrmem]]=1;
   dfs2(Mem[nrmem]);
  }
  nrmem--;
 }
 fout<<nrcomp<<"\n";
 for (i=1;i<=nrcomp;i++)
 {
  for (iaux=1;iaux<=n;iaux++)
   if (Grupe[iaux]==i)
    fout<<iaux<<" ";
  fout<<"\n";
 }
 return 0;
}


void dfs(int nod)
{
 Item *caut;
 int i2;
 caut=Adiac[nod].st;
 while (caut!=NULL)
 {
  i2=caut->val;
  if (Viz[i2]==0)
  {
   Viz[i2]=1;
   dfs(i2);
   nrmem++;
   Mem[nrmem]=i2;
  }
  caut=caut->next;
 }
}

void dfs2(int nod)
{
 Item *caut;
 int i2;
 caut=Adiac[nod].st;
 while (caut!=NULL)
 {
  i2=caut->val;
  if (Viz[i2]==0)
  {
   Grupe[i2]=nrcomp;
   Viz[i2]=1;
   dfs2(i2);
  }
  caut=caut->next;
 }
}