Pagini recente » Cod sursa (job #3148521) | Cod sursa (job #230250) | Cod sursa (job #2906120) | Cod sursa (job #3125462) | Cod sursa (job #1955225)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMax = 1e5 + 50;
const int inf = 2e9 + 5;
int N,M,nrComp;
int depth[NMax],lowPoint[NMax];
// depth[i] = adancimea nodului i in dfs
// lowPoint[i] = adancimea cea mai mica la care se poate ajunge
// dintr-un vecin al oricarui nod din subarborele lui i
vector<int> v[NMax];
vector<int> comp[NMax];
// v - liste de adiacenta
// comp[i] - nodurile din componenta biconexa cu numarul de ordine i
struct muchie {
int x,y;
muchie(int _x = 0,int _y = 0) {
x = _x;
y = _y;
}
bool equals(muchie b) {
return (x == b.x) && (y == b.y);
}
};
stack<muchie> st;
// st - stiva folosita pentu determinarea componentelor biconexe
void dfs(int,int);
void getComp(muchie);
int main() {
in>>N>>M;
for (int i=1;i<=M;++i) {
int x,y;
in>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
out<<nrComp<<'\n';
for (int i=1;i<=nrComp;++i) {
while (comp[i].size()) {
out<<comp[i].back()<<' ';
comp[i].pop_back();
}
out<<'\n';
}
in.close();out.close();
return 0;
}
void dfs(int nod,int dad) {
st.push(muchie(dad,nod));
depth[nod] = depth[dad] + 1;
lowPoint[nod] = depth[dad];
for (int k=0;k < (int)v[nod].size();++k) {
int next = v[nod][k];
if (next == dad) {
continue;
}
if (depth[next]) {
lowPoint[nod] = min(lowPoint[nod],depth[next]);
continue;
}
dfs(next,nod);
lowPoint[nod] = min(lowPoint[nod],lowPoint[next]);
// nod este punct de articulatie doar daca descendentii sai nu pot ajunge
// mai in sus pe graf decat prin el
// fiecare punct de articulatie determina o componenta biconexa
// in subarborele sau
if (lowPoint[next] == depth[nod]) {
getComp(muchie(nod,next));
}
}
}
void getComp(muchie m) {
++nrComp;
while (true) {
muchie aux = st.top();
comp[nrComp].push_back(aux.y);
if ( !aux.equals(m) ) {
st.pop();
}
else {
break;
}
}
comp[nrComp].push_back(st.top().x);
st.pop();
}