Pagini recente » Cod sursa (job #2397001) | Cod sursa (job #3173420) | Cod sursa (job #2645013) | Cod sursa (job #1375597) | Cod sursa (job #3181042)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int nrcmp,cnt,n,m,x,y,dfn[100001],low[100001],dad[100001];
vector<int>g[200001];
stack<int>s;
vector<vector<int> >copie;
void biconex(int u,int tata){
dfn[u]=low[u]=++cnt;
dad[u]=tata;
s.push(u);
for(int x:g[u]){
if(dfn[x]==0){
biconex(x,u);
low[u]=min(low[u],low[x]);
if(low[x]>=dfn[u]){
nrcmp++;
vector<int>linie;
while(s.top()!=x){
linie.push_back(s.top());
s.pop();
}
int var=s.top();
linie.push_back(s.top());s.pop();
linie.push_back(dad[var]);
copie.push_back(linie);
}
}
else{
if(x!=tata)low[u]=min(low[u],dfn[x]);
}
}
}
int main(){
fin>>n>>m;
for(int i=1;i<=m;i++){
fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
biconex(1,0);
fout<<nrcmp<<'\n';
for(int i=0;i<nrcmp;i++){
for(int j=0;j<copie[i].size();j++)fout<<copie[i][j]<<' ';
fout<<'\n';
}
}