Pagini recente » Cod sursa (job #2476016) | Cod sursa (job #2031484) | Cod sursa (job #2482087) | Cod sursa (job #1325477) | Cod sursa (job #2262196)
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N,M,k;
vector <int> G[Nmax],lvl,low,v,bic_comp[Nmax];
stack <pair <int,int> > st;
void read()
{
f>>N>>M;
int x,y;
while(M--)
{
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
lvl.resize(N+1);
low.resize(N+1);
}
void DFS(int node, int parent)
{
low[node]=lvl[node]=lvl[parent]+1;
for(const auto &it:G[node])
if(it!=parent)
{
if(!lvl[it])
{
st.push({node,it});
DFS(it,node);
low[node]=min(low[node],low[it]);
if(low[it]>=lvl[node])
{
v.clear();
int x,y;
do
{
x=st.top().first;
y=st.top().second;
st.pop();
v.push_back(x);
v.push_back(y);
}while(x!=node or y!=it);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
bic_comp[++k]=v;
}
}
else
low[node]=min(low[node],low[it]);
}
}
void print()
{
g<<k<<'\n';
for(int idx=1;idx<=k;++idx,g<<'\n')
for(const auto &it:bic_comp[idx])
g<<it<<' ';
}
int main()
{
read();
DFS(1,0);
print();
return 0;
}