Pagini recente » Cod sursa (job #1149416) | Cod sursa (job #2664009) | Cod sursa (job #504436) | Cod sursa (job #1093490) | Cod sursa (job #2579268)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMAX=100004;
vector <int>g[NMAX],ans;
vector <vector<int>>sol;
stack<pair<int,int>>s;
int n,m,low[NMAX],val[NMAX];
bool seen[NMAX];
void DFS(int node){
seen[node]=1;
for(auto y:g[node])
if(!seen[y]) DFS(y);
}
void add_sol(int a,int b){
vector<int>c;
int node1,node2;
do{
node1=s.top().first,node2=s.top().second;
s.pop();
c.push_back(node1),c.push_back(node2);
}while(node1!=a || node2!=b);
sol.push_back(c);
}
void dfs(int node,int nb){
val[node]=low[node]=nb;
for(auto y:g[node]){
if(val[y]==-1){
s.push({node,y});
dfs(y,nb+1);
low[node]=min(low[node],low[y]);
if(low[y]>=val[node]) add_sol(node,y);
}
else
low[node]=min(low[node],val[y]);
}
}
int main()
{
in>>n>>m;
for(int i=1,a,b;i<=m;i++){
in>>a>>b;
g[a].push_back(b),g[b].push_back(a);
}
/* for(int i=1;i<=n;i++)
if(!seen[i]){
ans.push_back(i);
DFS(i);
}
out<<ans.size()<<'\n';
for(auto y:ans)
out<<y<<" ";*/
memset(val,-1,sizeof(val));
dfs(1,0);
out<<sol.size()<<'\n';
for(int i=0;i<sol.size();i++){
sort(sol[i].begin(),sol[i].end());
vector<int>::iterator dr=unique(sol[i].begin(),sol[i].end());
for(vector<int>::iterator k=sol[i].begin();k!=dr;k++)
out<<*k<<" ";
out<<'\n';
}
return 0;
}