Pagini recente » Cod sursa (job #33612) | Cod sursa (job #83771) | Cod sursa (job #1902235) | Cod sursa (job #766726) | Cod sursa (job #2796792)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_set>
using namespace std;
int nodSursa;
int distante[100001];
vector<unordered_set<int>> componenteBiconexe;
vector<int> vizPasi;
vector<int> nivelMinimIntoarcere;
stack<pair <int, int>> StivaMuchiiComponentaBiconexaCurenta;
class Graf {
private:
int m_nrNoduri;
vector<vector<int>> m_listAdiacenta;
vector<int> viz;
public:
void citire(){
ifstream f("../biconex.in");
vector<int> aux;
int nrMuchii;
f>>this->m_nrNoduri;
this->m_listAdiacenta.assign(this->m_nrNoduri + 1, aux);
f>>nrMuchii;
for(int i=0; i<nrMuchii; i++){
int x,y;
f>>x>>y;
this->m_listAdiacenta[x].push_back(y);
this->m_listAdiacenta[y].push_back(x);
}
viz.assign(this->m_nrNoduri + 1, 0);
}
void prelucrare(int nod, int x){
//cout<<nod<<"\n";
distante[nod] = distante[x] + 1;
}
void BFS(int nod){
int curent;
queue<int> coada;
int viz[this->m_nrNoduri+1];
for(int i=1; i<=m_nrNoduri; i++){
viz[i] = 0;
}
coada.push(nod);
viz[nod] = 1;
prelucrare(nod, nod);
while(!coada.empty()){
curent = coada.front();
for(int i=0; i < this->m_listAdiacenta[curent].size(); i++){
if(viz[this->m_listAdiacenta[curent][i]] == 0){
coada.push(this->m_listAdiacenta[curent][i]);
prelucrare(coada.back(),curent);
viz[this->m_listAdiacenta[curent][i]] = 1;
}
}
coada.pop();
}
}
/*
void prelucrareDFS(int nod){
cout<<nod<<endl;
}
*/
void DFS(int nod){
//prelucrareDFS(nod);
viz[nod] = 1;
for(int i=0; i<this->m_listAdiacenta[nod].size(); i++){
if(viz[this->m_listAdiacenta[nod][i]] == 0){
DFS(this->m_listAdiacenta[nod][i]);
}
}
}
void afisDrumuri() {
ofstream g("../bfs.out");
for(int i=1; i <= this->m_nrNoduri; i++){
g<<distante[i] - 1<<" ";
}
}
void DFSBiconexe(int nodCurent, int precedent, int pas){
//marcam ca vizitat nodul curent
vizPasi[nodCurent] = pas;
//momentan nivelul minim de intoarcere e nivelul curent, adica pasul
nivelMinimIntoarcere[nodCurent] = pas;
//parcurgem vecinii nodului curent
for(int i=0; i<this->m_listAdiacenta[nodCurent].size(); i++){
int vecinCurent = this->m_listAdiacenta[nodCurent][i];
if(vecinCurent != precedent){
//verificam pe ce fel de muchie suntem
//daca vecinul curent a mai fost vizitat inseamna ca am dat de o muchie de intoarcere, altfel suntem pe o muchie in jos
if(vizPasi[vecinCurent] == -1){
//am dat de o noua muchie din componenta biconexa curenta, asa ca o adaugam in stiva
StivaMuchiiComponentaBiconexaCurenta.push(make_pair(nodCurent, vecinCurent));
//apelam DFS pentru vecinul curent
DFSBiconexe(vecinCurent, nodCurent, pas + 1);
//verificam daca atunci cand ne am dus mai departe in graf
// am dat de o muchie de intoarcere care ne duce mai sus decat ne ducea nodul acesta inainte
if(nivelMinimIntoarcere[nodCurent] > nivelMinimIntoarcere[vecinCurent]){
nivelMinimIntoarcere[nodCurent] = nivelMinimIntoarcere[vecinCurent];
}
//verificam daca am ajuns la finalul componentei biconexe
if(nivelMinimIntoarcere[vecinCurent] >= vizPasi[nodCurent]){
//trebuie sa adaugam noua componenta biconexa in vectorul de componenete biconexe
//si sa golim stiva cu muchiile componentei biconexe curente
unordered_set<int> aux;
int aux1, aux2;
do{
aux1 = StivaMuchiiComponentaBiconexaCurenta.top().first;
aux2 = StivaMuchiiComponentaBiconexaCurenta.top().second;
aux.insert(aux1);
aux.insert(aux2);
StivaMuchiiComponentaBiconexaCurenta.pop();
} while (aux1 != nodCurent || aux2 != vecinCurent);
componenteBiconexe.push_back(aux);
}
}else{
//avem o muchie de intoarcere, trebuie sa verificam daca nu cumva duce mai sus
if(nivelMinimIntoarcere[nodCurent] > vizPasi[vecinCurent]){
nivelMinimIntoarcere[nodCurent] = vizPasi[vecinCurent];
}
}
}
}
}
void afisComponenteBiconexe(){
ofstream g("../biconex.out");
vizPasi.assign(this->m_nrNoduri + 1, -1);
nivelMinimIntoarcere.resize(this->m_nrNoduri + 1);
DFSBiconexe(1,0,0);
g<<componenteBiconexe.size()<<"\n";
for(int i=0; i<componenteBiconexe.size(); i++){
for(unordered_set<int>::iterator it = componenteBiconexe[i].begin(); it != componenteBiconexe[i].end(); it++){
g<<*it<<" ";
}
g<<"\n";
}
}
};
int main() {
ofstream out("../biconex.out");
Graf g;
g.citire();
g.afisComponenteBiconexe();
return 0;
}