Pagini recente » Cod sursa (job #37642) | Cod sursa (job #1806567) | Cod sursa (job #3173036) | Cod sursa (job #1552427) | Cod sursa (job #1604151)
#include <iostream>
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define pair pair<int,int>
const int NMAX = 100000;
const int MMAX = 200000;
int n; int m;
vector<int> g[NMAX + 1];
vector<int> low(NMAX + 1, 0);
vector<int> lev(NMAX + 1, -1);
stack<pair> st;
vector< vector<int> > comp;
bitset<NMAX + 1> articulate;
vector<int> ret(NMAX + 1, 0);
int nrComp;
void read(vector<int>* g, int& n, int& m) {
fin >> n >> m;
for(int i = 1; i <= m; ++i) {
int x; int y;
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
}
void getComponents(stack<pair>& st, int nodeL, int nodeR) {
comp.push_back(vector<int>(0));
int x; int y;
do {
x = st.top().first;
y = st.top().second;
comp[nrComp].push_back(x);
comp[nrComp].push_back(y);
st.pop();
} while(st.empty() == false && !(x == nodeL && y == nodeR));
nrComp++;
}
void dfs(int node, int father, int level) {
lev[node] = low[node] = level;
for(int x : g[node]) {
if(x == father) continue;
if(lev[x] == -1) {
st.push({node, x}); //bagam muchiile in ordinea viztarii
dfs(x, node, level + 1);
low[node] = min(low[x], low[node]); //pot sa ma intorc pe arbore in jos si apoi pe o muchie de intoarcere
if(low[x] >= lev[node]) //la fii radacinii tot timpul intra low[fiu] > lev[radacina]
articulate[node] = true, getComponents(st, node, x); //tot subarborele e o componenta biconexa
/* 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 nodul curent, insemna ca nodul curent este punct de articulatie
(deconecteaza fiul + subarborele fiului fata de parinte)
Se pastreaza muchiile in ordinea parcurgerii. Componenta biconexa e formata din nodurile muchiilor dintre 2 puncte de
articulatie. Gasim punct de articulatie => golim stiva si formam componenta
*/
} else //e muchie de intoarcere, low e setat direct
low[node] = min(low[node], lev[x]);
}
}
void print() {
fout << nrComp << '\n';
for(vector<int> v : comp) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()) , v.end());
//unique scoate elementele duplicate, dar nu face resize, returneaza adresa urmatorului element dupa ultimul
//erase sterge intervalul specificiat inclusiv
for(int x : v)
fout << x << ' ';
fout << '\n';
}
}
int main() {
read(g, n, m);
dfs(1, 0, 0);
print();
return 0;
}