Cod sursa(job #2664775)

Utilizator patriciaxdBraica Patricia patriciaxd Data 29 octombrie 2020 12:27:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include    <bits/stdc++.h>
using namespace std;

//Algoritmul pentru componente tare conexe.
// Gasire si afisare
// Un graf este tare conex daca pentru orice varf din graf exista drum
// de la primul la al doilea si de la al doilea la primul
// La drum conteaza sensul si la lant nu (vorbind de grafurile orientate)
///Algoritmul lui Kosaraju
///Mod de rezolvare: Parcurgem graful cu un dfs dupa aceea construim transpusa grafului
/// si din nou facem dfs pe transpusa.
int N,M;//nr de varfuri si muchii
vector<int>Graf1[100001],Graf2[100001];//graful si transpusa lui
stack <int> stiva;//stiva in care punem varfurile din primul dfs in momentul cand din
// ele nu se mai poate merge niciunde (n-am inteles inca de ce)
short int vizitat[100001];//daca am vizitat varfurile
///Problema Componente tare conexe de pe infoarena
int Nrctc;//nr de componente tare conexe
vector <int> Ctc[100001];//elementele fiecarei componente
ifstream in("ctc.in");
ofstream out("ctc.out");
void citire()
{ in>>N>>M;
  for(int i=1;i<=M;i++)
  { int x,y;
    in>>x>>y;
    Graf1[x].push_back(y);
    Graf2[y].push_back(x);//construim transpusa
  }
}
void dfs1(int k)
{ vizitat[k]=1;
  for(size_t i=0;i<Graf1[k].size();i++)
  { int Vecin=Graf1[k][i];
    if(!vizitat[Vecin])
        dfs1(Vecin);
  }
  stiva.push(k);//in momentul cand se intoarce si iese din for nu mai are unde sa se duca
}
void dfs2(int k)
{ vizitat[k]=2;
  Ctc[Nrctc].push_back(k);
  for(int i=0;i<Graf2[k].size();i++)
  { int Vecin=Graf2[k][i];
     if(vizitat[Vecin]==1)
        dfs2(Vecin);
  }
}
void rezolvare()
{ for(int i=1;i<=N;i++)
     if(!vizitat[i])
        dfs1(i);
 while(!stiva.empty())
 { int nod=stiva.top();
     if(vizitat[nod]==1)
      {Nrctc++;
      dfs2(nod);
      }
     stiva.pop();
 }
}
void afisare()
{ out<<Nrctc<<'\n';
  for(int i=1;i<=Nrctc;i++)
    {for(int j=0;j<Ctc[i].size();j++)
        out<<Ctc[i][j]<<' ';
    out<<'\n';
    }
}
int main()
{ citire();
  rezolvare();
  afisare();
    return 0;
}