Pagini recente » Cod sursa (job #3277366) | Cod sursa (job #1524567) | Cod sursa (job #948445) | Cod sursa (job #2914386) | Cod sursa (job #2793630)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <bitset>
using namespace std;
const int NMAX = 100001;
class graf{
private:
int nrNoduri, nrMuchii;
vector<int> listaAd[NMAX];
bitset<NMAX> viz;
vector<vector<int>> ctc;
void dfsCompTareConexe(int nod, int &nivelCrt, vector<int> &nivel, vector<int> &nivelMin, stack<int> &s, bitset<NMAX> &inStiva);
public:
graf(int nrNoduri, int nrMuchii) : nrNoduri(nrNoduri), nrMuchii(nrMuchii) {};
void adaugaInListaAd(const int &nod1, const int &nod2);
vector<vector<int>> componenteTareConexe();
};
void graf::adaugaInListaAd(const int &nod1, const int &nod2) {
listaAd[nod1].push_back(nod2);
}
vector<vector<int>> graf :: componenteTareConexe() {
vector<int> nivel;
vector<int> nivelMin;
nivel.resize(NMAX);
nivelMin.resize(NMAX);
stack<int> s;
bitset<NMAX> inStiva;
int niv = 1;
for(int i = 1; i <= nrNoduri; i++){
if(!viz[i])
dfsCompTareConexe(i, niv, nivel, nivelMin, s, inStiva);
}
return ctc;
}
void graf::dfsCompTareConexe(int nod, int &nivelCrt, vector<int> &nivel, vector<int> &nivelMin, stack<int> &s, bitset<NMAX> &inStiva) {
viz[nod] = true;
s.push(nod);
inStiva[nod] = true;
nivel[nod] = nivelCrt;
nivelMin[nod] = nivelCrt;
nivelCrt++;
for(int i = 0; i < listaAd[nod].size(); i++) {
int vecin = listaAd[nod][i];
if (!viz[vecin]) {
dfsCompTareConexe(vecin, nivelCrt, nivel, nivelMin, s, inStiva);
nivelMin[nod] = min(nivelMin[nod], nivelMin[vecin]);
} else {
if (inStiva[vecin])
nivelMin[nod] = min(nivelMin[nod], nivel[vecin]);
}
}
if(nivelMin[nod] == nivel[nod]){
vector<int> compCrt;
int nodCompCrt;
do{
nodCompCrt = s.top();
compCrt.push_back(nodCompCrt);
s.pop();
inStiva[nodCompCrt] = false;
}while(nodCompCrt != nod);
ctc.push_back(compCrt);
}
}
int main() {
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;
fin >> n >> m;
graf G(n, m);
for(int i = 0; i < m; i ++){
int n1, n2;
fin >> n1 >> n2;
G.adaugaInListaAd(n1, n2);
}
vector<vector<int>> componente = G.componenteTareConexe();
fout<<componente.size()<<"\n";
for(int i = 0; i < componente.size(); i++) {
for(int j = 0; j < componente[i].size(); j++) {
fout<<componente[i][j]<<" ";
}
fout<<"\n";
}
return 0;
}