Pagini recente » Cod sursa (job #2358564) | Cod sursa (job #1073228) | Cod sursa (job #574949) | Cod sursa (job #1118169) | Cod sursa (job #2262184)
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N,M,k;
list <int> G[Nmax];
int lvl[Nmax];
int low[Nmax];
vector <int> v;
vector <int> 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);
}
}
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 and 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;
}