Pagini recente » Cod sursa (job #2882817) | Cod sursa (job #2561065) | Cod sursa (job #417459) | Cod sursa (job #3151065) | Cod sursa (job #2796830)
#include <bits/stdc++.h>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
class Graf{
private:
int nrNoduri;
vector<vector<int>> listaVecini;
public:
Graf();
Graf(int);
int get_nrNoduri();
void set_nrNoduri(int);
void set_listaVecini();
void adaugaMuchie(int, int);
// CTC
void Tarjan();
void DFS_CTC(int, vector<int>&, vector<int>&, stack<int>&, vector<bool>&, int&);
};
Graf::Graf(int n){
this->nrNoduri = n;
for (int i = 1; i <= nrNoduri; i++){
vector<int> aux;
listaVecini.push_back(aux);
}
}
Graf::Graf(){
}
void Graf::adaugaMuchie(int m1, int m2){
listaVecini[m1].push_back(m2);
}
int Graf::get_nrNoduri(){
return this->nrNoduri;
}
void Graf::set_nrNoduri(int n){
this->nrNoduri = n;
}
void Graf::set_listaVecini(){
for (int i = 1; i <= this->get_nrNoduri(); i++){
vector<int> aux;
listaVecini.push_back(aux);
}
}
void Graf::DFS_CTC(int nod_curent, vector<int> &descoperit, vector<int> &low, stack<int> &stiva, vector<bool> &membruStiva, int &nr){
static int timp = 0;
descoperit[nod_curent] = low[nod_curent] = timp++;
stiva.push(nod_curent);
membruStiva[nod_curent] = true;
for (auto elem: listaVecini[nod_curent]){
if (descoperit[elem] == -1){
DFS_CTC(elem, descoperit, low, stiva, membruStiva, nr);
}
if(membruStiva[elem] == true){
low[nod_curent] = min(low[nod_curent], low[elem]);
}
}
if (descoperit[nod_curent] == low[nod_curent]){
for (int nod = stiva.top();;nod = stiva.top()){
stiva.pop();
membruStiva[nod] = false;
low[nod] = descoperit[nod_curent];
if (nod == nod_curent)
break;
}
nr++;
}
}
void Graf::Tarjan(){
vector<int> descoperit(this->get_nrNoduri(), -1);
vector<int> low(this->get_nrNoduri(), -1);
stack<int> stiva;
vector<bool> membruStiva(this->get_nrNoduri(), false);
int nr = 0; // numarul componenetelor tare conexe
for (int i = 0; i < this->get_nrNoduri(); i++){
if (descoperit[i] == -1)
DFS_CTC(i, descoperit, low, stiva, membruStiva, nr);
}
g << nr << "\n";
set<int> multime;
for (int i = 0; i < this->get_nrNoduri(); i++){
multime.insert(low[i]);
}
for (auto elem : multime){
for (int i = 0; i < this->get_nrNoduri(); i++){
if (low[i] == elem)
g << i + 1<< " ";
}
g << "\n";
}
}
int main(){
Graf g1;
int n, m, nod1, nod2;
f >> n >> m;
g1.set_nrNoduri(n);
g1.set_listaVecini();
for (int i = 1; i <= m; i++){
f >> nod1 >> nod2;
g1.adaugaMuchie(nod1 - 1, nod2 - 1);
}
g1.Tarjan();
return 0;
}