Pagini recente » Cod sursa (job #540741) | Cod sursa (job #794988) | Cod sursa (job #306315) | Cod sursa (job #2646202) | Cod sursa (job #2876270)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define DIM 100000
int n, m, nrcomp, radacina, nr;
bool sel[DIM + 1], fr[DIM + 1];
int low[DIM + 1], nvl[DIM + 1], t[DIM + 1];
vector <int> G[DIM + 1];
vector <int> Comp[DIM + 1]; //retin fiecare componenta biconexa;
stack <pair<int, int>> St;
static inline void Save_comp(int x, int y) {
int st, dr;
nrcomp++;
do {
st = St.top().first;
dr = St.top().second;
Comp[nrcomp].push_back(st);
Comp[nrcomp].push_back(dr);
St.pop();
}while(x != st && y != dr && x != dr && y != st);
}
static inline void dfs(int nod) {
sel[nod] = 1;
low[nod] = nvl[nod];
for(auto e : G[nod]) {
if(e != t[nod] && nvl[e] < nvl[nod])
St.push({nod, e});
if(!sel[e]) {
nvl[e] = nvl[nod] + 1;
t[e] = nod;
dfs(e);
if(low[e] < low[nod])
low[nod] = low[e];
if(low[e] >= nvl[nod])
Save_comp(nod, e);
}else if(e != t[nod] && nvl[e] < low[nod])
low[nod] = nvl[e];
}
}
int main() {
fin.tie();
fout.tie();
fin >> n >> m;
for(int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
nvl[1] = 1;
dfs(1);
fout << nrcomp << '\n';
for(int i = 1; i <= nrcomp; i++) {
for(auto e : Comp[i])
if(!fr[e]) {
fout << e << " ";
fr[e] = 1;
}
fout << '\n';
for(int i = 1; i <= n; i++)
fr[i] = 0;
}
return 0;
}