Pagini recente » Cod sursa (job #352921) | Cod sursa (job #2431010) | Cod sursa (job #1480206) | Cod sursa (job #3216933) | Cod sursa (job #3188469)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
void formeaza_rezultat(int primul, int ultimul, stack<pair<int, int>>& muchii_componenta, vector<vector<int>>& componenta_biconexa) {
set<int> component_set;
vector<int> component;
pair<int, int> muchie;
do {
muchie = muchii_componenta.top(); muchii_componenta.pop();
component_set.insert(muchie.first);
component_set.insert(muchie.second);
} while (muchie != make_pair(primul, ultimul) && muchie != make_pair(ultimul, primul));
component.assign(component_set.begin(), component_set.end());
componenta_biconexa.push_back(component);
}
void dfs(int nod_curent, int parinte, const vector<vector<int>>& lista_vecini, int discovery_time[], int lowest[], bool vizitate[], stack<pair<int, int>>& muchii_componenta, vector<vector<int>>& componenta_biconexa) {
static int timeCounter = 0;
vizitate[nod_curent] = true;
discovery_time[nod_curent] = lowest[nod_curent] = ++timeCounter;
for (int vecin : lista_vecini[nod_curent]) {
if (vecin != parinte) {
if (!vizitate[vecin]) {
muchii_componenta.push({nod_curent, vecin});
dfs(vecin, nod_curent, lista_vecini, discovery_time, lowest, vizitate, muchii_componenta, componenta_biconexa);
lowest[nod_curent] = min(lowest[nod_curent], lowest[vecin]);
if (lowest[vecin] >= discovery_time[nod_curent]) {
formeaza_rezultat(vecin, nod_curent, muchii_componenta, componenta_biconexa);
}
} else {
lowest[nod_curent] = min(lowest[nod_curent], discovery_time[vecin]);
}
}
}
}
int main() {
int numar_noduri, numar_muchii;
fin >> numar_noduri >> numar_muchii;
vector<vector<int>> lista_vecini(numar_noduri + 1);
int discovery_time[100000] = {0}, lowest[100000] = {0};
bool vizitate[100000] = {false};
vector<vector<int>> componenta_biconexa;
stack<pair<int, int>> muchii_componenta;
for (int i = 0; i < numar_muchii; i++) {
int nod1, nod2;
fin >> nod1 >> nod2;
lista_vecini[nod1].push_back(nod2);
lista_vecini[nod2].push_back(nod1);
}
dfs(1, 0, lista_vecini, discovery_time, lowest, vizitate, muchii_componenta, componenta_biconexa);
fout << componenta_biconexa.size() << '\n';
for (vector<int> comp : componenta_biconexa) {
for (int nod : comp)
fout << nod << ' ';
fout << '\n';
}
return 0;
}