Pagini recente » Cod sursa (job #2586917) | Cod sursa (job #1619984) | Cod sursa (job #2512244) | Cod sursa (job #1648418) | Cod sursa (job #2562935)
#include <bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<pair<int, int>>a[N];
vector<int>g[N], sol[N];
stack<pair<int,int>>st;
pair<int, int>muches[2*N];
int v[N],v2[N],k=-1, vm[2*N];
void dfs(int i, int j=0, int mucia=0){
v[i]=i;
st.push({i,mucia});
for(auto it:a[i]){
if(!v[it.first]){
dfs(it.first,i,it.second);
}
else if(v[it.first] && it.first!=j){
vm[it.second]=1;
while(!st.empty() && st.top().first!=v[it.first]){
g[v[it.first]].push_back(st.top().first);
g[st.top().first].push_back(v[it.first]);
v[st.top().first]=v[it.first];
vm[st.top().second]=1;
st.pop();
}
}
}
if(!st.empty() && st.top().first==i){
st.pop();
}
}
void dfs2(int i){
sol[k].push_back(i);
v2[i]=1;
for(auto it:g[i]){
if(!v2[it]){
dfs2(it);
}
}
}
int main(){
int n, m,x,y;
in>>n>>m;
for(int i=1; i<=m; ++i){
in>>x>>y;
muches[i]={x,y};
a[x].push_back({y,i});
a[y].push_back({x,i});
}
dfs(1);
for(int i=1; i<=n; ++i){
if(!v2[i]){
++k;
dfs2(i);
if(sol[k].size()==1){
--k;
}
}
}
for(int i=1; i<=m; ++i){
if(!vm[i]){
sol[++k].clear();
sol[k].push_back(muches[i].first);
sol[k].push_back(muches[i].second);
}
}
out<<k+1<<"\n";
for(int i=0; i<=k; ++i){
for(auto it:sol[i]){
out<<it<<" ";
}
out<<"\n";
}
return 0;
}