Pagini recente » Cod sursa (job #2861817) | Cod sursa (job #2855812) | Cod sursa (job #1465684) | Cod sursa (job #1399991) | Cod sursa (job #2876321)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define DIM 100000
int n, m, nrcomp;
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) {
pair<int, int> Nodes1 = {x, y}, Nodes2 = {y, x}, Nod;
nrcomp++;
do {
Nod = St.top();
Comp[nrcomp].push_back(Nod.first); //scot toate muchiile din stiva pana ajung la muchia x, y sau y, x;
Comp[nrcomp].push_back(Nod.second);
St.pop();
}while(Nod != Nodes1 && Nod != Nodes2);
}
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++) {
sort(Comp[i].begin(), Comp[i].end());
for(auto e : Comp[i])
if(!fr[e]) {
fout << e << " ";
fr[e] = 1;
}
fout << '\n';
for(auto e : Comp[i])
fr[e] = 0; //resetez nodurile afisate;
}
return 0;
}