Pagini recente » Cod sursa (job #803727) | Cod sursa (job #2832573)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N;
int M;
int start;
vector<vector<int>> vecini;
void citire_graf() {
f >> N;
f >> M;
int nod1, nod2;
vecini.resize(N + 1);
for (int i = 0; i < M; i++) {
f >> nod1 >> nod2;
vecini[nod1].push_back(nod2);
vecini[nod2].push_back(nod1);
}
}
void DFS_biconex(vector<bool>& vizitat, int fiu, int tata, vector<int>& nivel, vector<int>& low, stack<int>& stack, vector<vector<int>>& compConexe, int& nrCC) {
vizitat[fiu] = true;
stack.push(fiu);
nivel[fiu] = nivel[tata] + 1;
low[fiu] = nivel[fiu];
int i;
for (i = 0; i < vecini[fiu].size(); i++)
if (vecini[fiu][i] != tata) {//mergem depth, nu in sus, evitam sa mergem in sus
if (vizitat[vecini[fiu][i]] == true) {//daca am mai vizitat nodul, ii vedem val de low,
//daca e mai mare ca a nodului cu care e legat, luam valoarea aceea mai mica
if (low[fiu] > nivel[vecini[fiu][i]])
low[fiu] = nivel[vecini[fiu][i]];
}
else {
DFS_biconex(vizitat, vecini[fiu][i], fiu, nivel, low, stack, compConexe, nrCC);//altfel, nevizitat si mergem in continuare cu un DFS, iar tata devine fiu, fiu devine next vecin al fiului initial
if (low[fiu] > low[vecini[fiu][i]]) //low de la tatal nod merge in jos la fiu practic in cazul in care fiul are low mai mare
low[fiu] = low[vecini[fiu][i]];
if (nivel[fiu] <= low[vecini[fiu][i]]) {//cand nivel tata ajunge (maxim) egal cu low de vecin,in genere egal, inseamna ca avem back path si putem forma componentele conexe, ca am gasit ciclu si nod de articulatie
while (stack.top() != vecini[fiu][i]) {
compConexe[nrCC].push_back(stack.top());//scoatem din stiva rand pe rand elementele afara de fiu si tata si le retinem in vectorul de componente conexe
stack.pop();
}
compConexe[nrCC].push_back(vecini[fiu][i]);
stack.pop();
compConexe[nrCC].push_back(fiu);
nrCC++;
}
}
}
}
void biconex_init_si_print() {
vector<bool> vizitat(N + 1, false);
vector<int> nivel(N + 1);//vector de nivele
nivel[0] = 0;
vector<int> low(N + 1);//vector de low level pentru fiecare nod
low[0] = 0;
stack<int> stack; //stiva cu nodurile vizitate
vector<vector<int>> compConexe;
compConexe.resize(N + 1);
int tata = 0;
int fiu = 1;
int nrCC = 0;
DFS_biconex(vizitat, fiu, tata, nivel, low, stack, compConexe, nrCC);
g << nrCC << '\n';
for (int i = 0; i < nrCC; i++) {
for (int j = 0; j < compConexe[i].size(); j++)
g << compConexe[i][j] << " ";
g << '\n';
}
}
int main()
{
citire_graf();
biconex_init_si_print();
return 0;
}