Pagini recente » Cod sursa (job #639978) | Cod sursa (job #2939579) | Cod sursa (job #1091562) | Cod sursa (job #2397605) | Cod sursa (job #2864154)
#include <fstream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <vector<int>> S;
vector <int> v[100011];
stack <pair<int,int>> q;
void component(int x,int y)
{
vector <int> s;
int ix,iy;
do
{
ix=q.top().first;
iy=q.top().second;
s.push_back(ix);
s.push_back(iy);
q.pop();
}while(ix!=x && iy!=y);
S.push_back(s);
}
int when[100011],low[100011],part[100011];
void dfs(int nod,int tata,int k)
{
when[nod]=low[nod]=k;
for(int i=0;i<v[nod].size();i++)
{
if(v[nod][i]==tata)
continue;
if(when[v[nod][i]]==-1)
{
q.push(make_pair(nod,v[nod][i]));
dfs(v[nod][i],nod,k+1);
low[nod]=min(low[nod],low[v[nod][i]]);
if(low[v[nod][i]]>=when[nod])
{
part[nod]++;
component(nod,v[nod][i]);
}
}
else
low[nod]=min(low[nod],when[v[nod][i]]);
}
}
int n,m,x,y,i,j;
int main()
{
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1;i<=n;i++)
when[i]=-1;
dfs(1,0,0);
g<<S.size()<<'\n';
for(i=0;i<S.size();i++)
{
sort(S[i].begin(),S[i].end());
g<<S[i][0]<<" ";
for(j=1;j<S[i].size();j++)
if(S[i][j]!=S[i][j-1])
g<<S[i][j]<<" ";
g<<'\n';
}
return 0;
}