Pagini recente » Cod sursa (job #1369424) | Cod sursa (job #1130438) | Cod sursa (job #1729843) | Cod sursa (job #1240739) | Cod sursa (job #2801993)
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
ifstream in("biconex.in");
ofstream out("biconex.out");
set<int> ans1;
vector<int> v[100001];
stack<pair<int,int> > st;
vector<pair<int,int> > cbi[100001];
int depth[100001],parc[100001],ans;
int dfs(int node)
{
parc[node]=1;
int up=(1<<30);
for(auto i : v[node])
{
st.push(make_pair(node,i));
if(parc[i]==1)
{
if(depth[node]<=depth[i])
st.pop();
up=min(up,depth[i]);
continue;
}
else
{
depth[i]=depth[node]+1;
int nodeant=dfs(i);
up=min(up,nodeant);
if(nodeant>=depth[node])
{
++ans;
while(st.size() && st.top() != mp(node,i))
{
cbi[ans].push_back(st.top());
st.pop();
}
cbi[ans].push_back(st.top());
st.pop();
}
}
}
return up;
}
int main()
{
int n,m,i,x,y;
in>>n>>m;
for(i=1; i<=m; ++i)
{
in>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1);
out<<ans<<'\n';
for(i=1; i<=ans; ++i)
{
for(auto j : cbi[i])
{
if(ans1.find(j.first) == ans1.end())
ans1.insert(j.first);
if(ans1.find(j.second) == ans1.end())
ans1.insert(j.second);
}
for(auto j : ans1)
out<<j<<" ";
out<<'\n';
ans1.clear();
}
return 0;
}