Pagini recente » Cod sursa (job #2957684) | Cod sursa (job #439290) | Cod sursa (job #575584) | Cod sursa (job #575580) | Cod sursa (job #2796662)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <deque>
#include <stack>
using namespace std;
class Graf {
vector<list<int>> noduri;
void dfs(int nod, vector<bool> &vizitate) {
vizitate[nod] = true;
for(auto i: noduri[nod])
if(!vizitate[i])
dfs(i, vizitate);
}
void bfs(int start, vector<int> &costuri, vector<bool> &vizitate,deque<int> &coada) {
coada.push_back(start);
vizitate[start] = true;
costuri[start] = 0;
while(coada.empty() != 1) {
int k = coada.front();
for(auto i: noduri[k])
if(!vizitate[i]) {
costuri[i] += (costuri[k] + 1);
vizitate[i] = true;
coada.push_back(i);
}
coada.pop_front();
}
}
void dfsTopo(int nod, vector<bool> &vizitate, stack<int> &rezultat) {
vizitate[nod] = true;
for(auto i: noduri[nod])
if(!vizitate[i])
dfsTopo(i, vizitate, rezultat);
rezultat.push(nod);
}
void dfsBiconex(int nod, int tata, int &nrSolutii, vector<bool> &vizitate, int nivel[], int nma[], stack<int> &stiva, vector<int> solutie[]) {
vizitate[nod] = 1;
nma[nod] = nivel[nod] = nivel[tata] + 1;
stiva.push(nod);
for (auto x: noduri[nod]) {
if (x != tata){
if (vizitate[x])
nma[nod] = min(nma[nod], nivel[x]);
else{
dfsBiconex(x, nod, nrSolutii, vizitate, nivel, nma, stiva, solutie);
nma[nod] = min(nma[nod], nma[x]);
if (nma[x] >= nivel[nod]) {
nrSolutii++;
while (stiva.top() != x) {
solutie[nrSolutii].push_back(stiva.top());
stiva.pop();
}
solutie[nrSolutii].push_back(x);
stiva.pop();
solutie[nrSolutii].push_back(nod);
}
}
}
}
}
public:
Graf(vector<list<int>> _noduri) : noduri(_noduri) {}
friend ostream& operator<< (ostream& os, Graf graf) {
os << graf.noduri.size() << " nodes\n";
for(int i = 0; i < graf.noduri.size(); i++) {
os << "node " << i << ": ";
for(int j: graf.noduri[i])
os << j << " ";
os << "\n";
}
return os;
}
int nrConexe() {
vector<bool> vizitate(noduri.size());
int nr = 0;
for(int i = 0; i < noduri.size(); i++)
if(!vizitate[i]) {
nr++;
dfs(i, vizitate);
}
return nr;
}
void costuriBFS(int nod, ostream& os = cout) {
vector<int> costuri(noduri.size());
deque<int> coada;
vector<bool> vizitate(noduri.size());
bfs(nod, costuri, vizitate, coada);
for (int i = 0; i < noduri.size(); i++) {
if(vizitate[i])
os << costuri[i] << " ";
else os << -1 << " ";
}
}
void sortareTopologica(ostream& os = cout){
vector<bool> vizitate(noduri.size());
stack<int> rezultat;
for(int i = 0; i < noduri.size(); i++)
if(!vizitate[i])
dfsTopo(i, vizitate, rezultat);
while(rezultat.empty() != 1){
os << rezultat.top() + 1 << " ";
rezultat.pop();
}
}
void componenteBiconexe(ostream& os = cout){
vector<bool> vizitate(noduri.size());
vector<int> solutie[noduri.size()];
stack<int> stiva;
int nivel[noduri.size()], nma[noduri.size()];
int nrSolutii = 0;
for (int i = 0; i < noduri.size(); i++)
if (vizitate[i] == 0)
dfsBiconex(i, 0, nrSolutii, vizitate, nivel, nma, stiva, solutie);
os << nrSolutii << "\n";
for (int i = 1; i <= nrSolutii; i++) {
for (auto j: solutie[i])
os << j + 1 << " ";
os << "\n";
}
}
};
int main() {
ifstream in("biconex.in");
ofstream out("biconex.out");
int noduri, muchii, start;
in >> noduri >> muchii;
// in >> start; //doar ptr bfs
vector<list<int>> aux(noduri);
for(int i = 0; i < muchii; i++) {
int x1, x2;
in >> x1 >> x2;
aux[x1 - 1].push_back(x2 - 1);
aux[x2 - 1].push_back(x1 - 1); // daca e neorientat
}
Graf graf(aux);
// out << graf.nrConexe(); //ptr DFS
// graf.costuriBFS(start - 1, out); //ptr BFS
// graf.sortareTopologica(out); //sortare topologica
graf.componenteBiconexe(out); //componente Biconexe
return 0;
}