Pagini recente » Cod sursa (job #878379) | Cod sursa (job #929502) | Cod sursa (job #215148) | Cod sursa (job #832400) | Cod sursa (job #2790681)
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
string prob="biconex";
ifstream in(prob+".in");
ofstream out(prob+".out");
struct edge{
int x,y;
edge(int _x,int _y){
x=_x;
y=_y;
}
};
struct node{
bool viz;
int ind,lowlink;
vector<edge*> e;
} noduri[nmax];
stack<edge*> s;
int ind=1;
vector<unordered_set<int>> res;
int p[nmax];
void dfs(int nod){
//cout<<nod<<' ';
noduri[nod].viz=1;
noduri[nod].ind=noduri[nod].lowlink=ind++;
for(auto e:noduri[nod].e){
int urm=e->x;
if(urm==nod)urm=e->y;
if(!noduri[urm].viz){
p[urm]=nod;
s.push(e);
dfs(urm);
noduri[nod].lowlink=min(noduri[nod].lowlink,noduri[urm].lowlink);
if((p[nod]!=0&&noduri[urm].lowlink>=noduri[nod].ind)||(p[nod]==0&&noduri[nod].e.size()>1)){
unordered_set<int> tmp;
while(s.top()!=e){
tmp.insert(s.top()->x);
tmp.insert(s.top()->y);
s.pop();
}
tmp.insert(s.top()->x);
tmp.insert(s.top()->y);
s.pop();
res.push_back(tmp);
}
}
else if(urm!=p[nod]){
noduri[nod].lowlink=min(noduri[nod].lowlink,noduri[urm].ind);
}
}
}
int main(){
int n,m;
in>>n>>m;
int x,y;
while(m--){
in>>x>>y;
edge *tmp=new edge(x,y);
noduri[x].e.push_back(tmp);
noduri[y].e.push_back(tmp);
}
dfs(1);
out<<res.size()<<'\n';
for(auto i:res){
for(auto j:i)out<<j<<' ';
out<<'\n';
}
}