Pagini recente » Cod sursa (job #735246) | Cod sursa (job #512858) | Cod sursa (job #173295) | Cod sursa (job #2297692) | Cod sursa (job #1213969)
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
#include <set>
#define DIM 100010
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> L[DIM];
bitset<DIM> V;
stack<pair<int, int> > S;
set<int> R[DIM];
set<int>::iterator it;
int Low[DIM];
pair<int, int> p;
int n, m, i, j, x, y, cbc;
void dfs(int nod, int niv, int tata) {
V[nod] = 1;
Low[nod] = niv;
for (int i=0;i<L[nod].size(); i++) {
int fiu = L[nod][i];
if (fiu == tata)
continue;
if (V[fiu] == 0) {
S.push(make_pair(nod, fiu));
dfs(fiu, niv+1, nod);
Low[nod] = min(Low[nod], Low[fiu]);
// tocmai m-am intors din fiul x al lui nod
if (Low[fiu] >= niv) {
// am componenta biconexa provocata de muchia nod,x
// scot din stiva tot ce am pus dupa muchia nod,x inclusiv
cbc ++;
do {
p = S.top();
S.pop();
R[cbc].insert(p.first);
R[cbc].insert(p.second);
} while (nod != p.first || fiu!=p.second);
}
} else
Low[nod] = min(Low[nod], Low[fiu]);
}
}
int main () {
fin>>n>>m;
for (i=1;i<=m;i++) {
fin>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
for (i=1;i<=n;i++) {
if (!V[i])
dfs(i, 1, 0);
}
fout<<cbc<<"\n";
for (i=1;i<=cbc;i++) {
for (it = R[i].begin(); it!=R[i].end(); it++) {
fout<<*it<<" ";
}
fout<<"\n";
}
return 0;
}