Pagini recente » Cod sursa (job #1841991) | Clasamentul arhivei de probleme | Cod sursa (job #2943709) | Borderou de evaluare (job #2015965) | Cod sursa (job #1691203)
/*
- Daca dintr-un fiu al nodului curent nu putem ajunge pe arbore in jos si apoi pe o muhcie de intoarcere
la un nod mai sus de cel curent, atunci nodul curent este punct de articulatie
- Componenta biconexa e formata din nodurile muchiilor dintre 2 puncte de articulatie.
- Cand gasim un punct de articulatie, golim stiva si retinem componenta
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define nMax 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
vector <int> lvl; //nivelul fiecarui nod in arborele DFS
vector <int> low; //nivelul minim
vector <int> graph[nMax];
vector < vector <int> > CBlist; //vectorul componentelor biconexe
stack < pair <int, int> > st;
void citire() {
int x, y;
f >> n >> m;
for (int i = 0; i < m; i++) {
f >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
}
int getMin (int x, int y) {
if (x < y) return x;
else return y;
}
void compBiconexe(int x, int y) {
vector <int> currCompB;
pair <int, int> current;
do {
current = st.top();
st.pop();
currCompB.push_back(current.second);
}
while (current.first != x && current.second != y);
currCompB.push_back(current.first);
CBlist.push_back(currCompB);
}
void DFS(int x) {
int level, i;
low[x] = lvl[x];
for (i = 0; i < graph[x].size(); i++) { //iterez prin vecinii nodului x
level = graph[x][i];
if (!lvl[level]) {
lvl[level] = lvl[x] + 1;
st.push(make_pair(x, level)); //punem muchiile in stiva in ordinea in care le vizitam
DFS(level);
low[x] = getMin(low[x], low[level]);
if (lvl[x] <= low[level])
compBiconexe(x, level);
}
else low[x] = getMin(low[x], lvl[level]); //e muchie de intoarcere
}
}
int main() {
citire();
lvl.resize(n + 1, 0);
low.resize(n + 1, 0);
for (int i = 1; i <= n; i++)
if (!lvl[i]) {
lvl[i] = 1;
DFS(i);
}
g << CBlist.size() << endl;
for (int i = 0; i < CBlist.size(); i++) {
for (int j = 0; j < CBlist[i].size(); j++)
g << CBlist[i][j] << " ";
g << endl;
}
return 0;
}