Pagini recente » Cod sursa (job #3198055) | Cod sursa (job #2059457) | Cod sursa (job #3163240) | Cod sursa (job #1827483) | Cod sursa (job #3188463)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
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) {
vector<int> component;
pair<int, int> muchie;
do {
muchie = muchii_componenta.top(); muchii_componenta.pop();
component.push_back(muchie.first);
component.push_back(muchie.second);
} while (muchie != make_pair(primul, ultimul) && muchie != make_pair(ultimul, primul));
componenta_biconexa.push_back(component);
}
void dfs(int nod_curent, int parinte, vector<vector<int>> lista_vecini, int discovery_time[], int lowest[], bool vizitate[], stack<pair<int, int>>& muchii_componenta, vector<vector<int>>& componenta_biconexa) {
vizitate[nod_curent] = true;
lowest[nod_curent] = discovery_time[nod_curent];
for (int vecin : lista_vecini[nod_curent]) {
if (vecin != parinte) {
if (discovery_time[nod_curent] > discovery_time[vecin]) {
muchii_componenta.push({nod_curent, vecin});
}
if (!vizitate[vecin]) {
discovery_time[vecin] = discovery_time[nod_curent] + 1;
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 if (vecin != parinte) {
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], lowest[100000];
bool vizitate[100000];
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);
}
discovery_time[1] = 1;
dfs(1, 0, lista_vecini, discovery_time, lowest, vizitate, muchii_componenta, componenta_biconexa);
cout << componenta_biconexa.size() << '\n';
for (vector<int> comp : componenta_biconexa) {
vector<bool> printat_deja(numar_noduri, false);
for (int nod : comp) {
if (!printat_deja[nod]) {
fout << nod << ' ';
printat_deja[nod] = true;
}
}
fout << '\n';
}
return 0;
}