Pagini recente » Cod sursa (job #3153618) | Cod sursa (job #3283174) | Cod sursa (job #2634859) | Cod sursa (job #1947026) | Cod sursa (job #3207571)
#include <fstream>
#include <vector>
#define NMAX 100000
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int globalTime;
struct type_stack{
int a, b;
}stiva[NMAX + 1];
int k, nrComp;
vector<int>comp[NMAX + 1];
struct type_node{
int d, l;
vector<int>edge;
}graf[NMAX + 1];
void findComponent(int nod) {
nrComp++;
while(stiva[k].a != nod)
comp[nrComp].push_back(stiva[k--].b);
comp[nrComp].push_back(stiva[k].b);
comp[nrComp].push_back(stiva[k].a);
k--;
}
void dfs(int nod, int p) {
globalTime++;
graf[nod].d = graf[nod].l = globalTime;
for(auto copil : graf[nod].edge) {
if(copil == p)
continue;
if(graf[copil].d != 0) {
graf[nod].l = min(graf[nod].l, graf[copil].d);
} else {
k++;
stiva[k].a = nod;
stiva[k].b = copil;
dfs(copil, nod);
graf[nod].l = min(graf[nod].l, graf[copil].l);
if(graf[nod].d <= graf[copil].l) {
findComponent(nod);
}
}
}
}
signed main() {
int n, m, a, b;
cin>>n>>m;
while(m--) {
cin>>a>>b;
graf[a].edge.push_back(b);
graf[b].edge.push_back(a);
}
dfs(1, 0);
cout<<nrComp<<"\n";
while(nrComp--) {
for(auto nod : comp[nrComp + 1]) {
cout<<nod<<" ";
}
cout<<"\n";
}
return 0;
}