Pagini recente » Cod sursa (job #779641) | Cod sursa (job #867304) | Cod sursa (job #969748) | Cod sursa (job #2287080) | Cod sursa (job #2262209)
#include <bits/stdc++.h>
#define Nmax 100001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N,M;
vector <int> G[Nmax],lvl,low,v;
vector <vector <int> > bic_comp;
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);
bic_comp.push_back(v);
}
}
else
low[node]=min(low[node],low[it]);
}
}
void print()
{
g<<bic_comp.size()<<'\n';
for(size_t i=0;i<bic_comp[i].size();++i)
{
sort(bic_comp[i].begin(),bic_comp[i].end());
bic_comp[i].erase(unique(bic_comp[i].begin(),bic_comp[i].end()),bic_comp[i].end());
for(size_t j=0;j<bic_comp[i].size();++j)
g<<bic_comp[i][j]<<' ';
g<<'\n';
}
}
int main()
{
read();
DFS(1,0);
print();
return 0;
}