Pagini recente » Cod sursa (job #1372214) | Cod sursa (job #1339940) | Cod sursa (job #95587) | Cod sursa (job #175030) | Cod sursa (job #1921353)
#include <bits/stdc++.h>
using namespace std;
int nxt;
int disc[100005], low[100005];
stack < pair<int, int> > s;
bool viz[100005];
vector < vector <int> > cmp;
vector <int> ax;
vector <int> adj[100005];
void dfs(int node, int parent){
++nxt;
disc[node] = low[node] = nxt;
s.push({parent, node});
viz[node] = 1;
for(auto it : adj[node]){
if(viz[it] == 0){
dfs(it, node);
low[node] = min(low[node], low[it]);
if(low[it] >= disc[node] || (parent == 0 && adj[node].size() > 1)){
int x, y;
ax.clear();
do{
x = s.top().first;
y = s.top().second;
ax.push_back(x);
ax.push_back(y);
s.pop();
}while(x != node || y != it);
cmp.push_back(ax);
}
}else if(it != parent){
low[node] = min(low[node], low[it]);
}
}
}
int main(){
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,i,x,y;
fin>>n>>m;
for(i = 1;i <= m;i++){
fin>>x>>y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1, 0);
fout<<cmp.size()<<'\n';;
for(auto &v : cmp){
sort(v.begin(), v.end());
auto it = unique(v.begin(), v.end());
v.resize(it - v.begin());
for(auto it : v){
fout<<it<<' ';
}
fout<<'\n';
}
return 0;
}