Pagini recente » Cod sursa (job #3132104) | Cod sursa (job #1310506) | Cod sursa (job #434070) | Cod sursa (job #403627) | Cod sursa (job #3275224)
#include <fstream>
#include <vector>
#include <set>
#include <stack>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int N=2e5+1;
vector<int>adj[N];
vector<set<int>>comp(N);
int n,m;
stack<pair<int,int>>st;
int height[N],low[N];
int cnt=0;
bool viz[N];
void sterge(int a,int b)
{
cnt++;
int tx=-1,ty=-1;
do
{
tx=st.top().first;
ty=st.top().second;
st.pop();
comp[cnt].insert(tx);
comp[cnt].insert(ty);
}
while(tx!=a&&ty!=b);
}
void dfs(int nod,int p)
{
viz[nod]=true;
height[nod]=height[p]+1;
low[nod]=height[nod];
for(auto u:adj[nod])
{
if(u==p)
continue;
if(viz[u]==true)
{
low[nod]=min(low[nod],height[u]);
}
else
{
st.push({nod,u});
dfs(u,nod);
if(low[u]>=height[nod])
{
sterge(nod,u);
}
low[nod]=min(low[nod],low[u]);
}
}
}
int main()
{
cin>>n>>m;
for(int i=1; i<=m; i++)
{
int a,b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(1,0);
cout<<cnt<<'\n';
for(int i=1;i<=cnt;i++)
{
for(auto u:comp[i])
cout<<u<<" ";
cout<<'\n';
}
return 0;
}