Pagini recente » Cod sursa (job #1884975) | Clasament lot_2018_baraj_1 | Cod sursa (job #950966) | Cod sursa (job #185031) | Cod sursa (job #2343253)
#include <bits/stdc++.h>
using namespace std;
#define LMAX 100001
int n,m;
vector<int> G[LMAX];
int time_disc=0,low[LMAX],disc[LMAX];
stack<pair<int,int> > st;
int nr_comp=0;
vector<int> C[LMAX];
void make_component(pair<int,int> edge){
++nr_comp;
pair<int,int> it;
do{
it=st.top();
st.pop();
C[nr_comp].push_back(it.first);
C[nr_comp].push_back(it.second);
}while(it!=edge);
sort(C[nr_comp].begin(),C[nr_comp].end());
C[nr_comp].resize(distance(C[nr_comp].begin(),unique(C[nr_comp].begin(),C[nr_comp].end())));
}
void dfs(int node,int parent){
disc[node]=low[node]=(++time_disc);
for(auto it : G[node]){
if(it==parent) continue;
else if(!disc[it]){
st.push({node,it});
dfs(it,node);
low[node]=min(low[node],low[it]);
if(low[it]>=disc[node])
make_component({node,it});
}
else low[node]=min(low[node],disc[it]);
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i){
int u,v;
scanf("%d %d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,-1);
printf("%d\n",nr_comp);
for(int i=1;i<=nr_comp;++i){
for(auto it : C[i])
printf("%d ",it);
printf("\n");
}
return 0;
}