Pagini recente » Cod sursa (job #3166272) | Cod sursa (job #2348211) | Cod sursa (job #2664775)
#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;
}