Pagini recente » Cod sursa (job #1476318) | Cod sursa (job #2374423) | Cod sursa (job #1955454) | Cod sursa (job #2825184) | Cod sursa (job #2762191)
#include <bits/stdc++.h>
#define nmax 100001
#define mmax 200001
using namespace std;
string prob="biconex";
ifstream in(prob+".in");
ofstream out(prob+".out");
struct node{
int index,lowlink;
} noduri[nmax];
int ind=1;
stack<int> s;
vector<unordered_set<int> > res;
vector<int> graf[nmax];
void dfs(int nod){
noduri[nod].index=noduri[nod].lowlink=ind++;
s.push(nod);
for(auto i:graf[nod]){
if(noduri[i].index)noduri[nod].lowlink=min(noduri[i].index,noduri[nod].lowlink);
}
for(auto i:graf[nod]){
if(!noduri[i].index){
s.push(nod);
dfs(i);
noduri[nod].lowlink=min(noduri[i].lowlink,noduri[nod].lowlink);
if(noduri[i].lowlink==noduri[nod].index){
int n;
unordered_set<int> tmp;
do{
n=s.top();
tmp.insert(n);
s.pop();
}while(n!=nod);
if(tmp.size()!=1)res.push_back(tmp);
}
}
}
}
int main(){
int n,m;
in>>n>>m;
for(;m;m--){
int x,y;
in>>x>>y;
graf[x].push_back(y);
graf[y].push_back(x);
}
for(int i=1;i<=n;i++){
if(!noduri[i].index){
dfs(i);
}
}
out<<res.size()<<'\n';
for(auto i:res){
for(auto j:i)out<<j<<' ';
out<<'\n';
}
}