Pagini recente » Cod sursa (job #1486570) | Cod sursa (job #294446) | Cod sursa (job #483209) | Cod sursa (job #2240249) | Cod sursa (job #2721656)
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,inapoi[100005],grad[100005],nr=0,tr=0,stiva[100005];
bool fost[100005];
vector<int>vecini[100005],sol[100005];
void dfs(int nod,int tata)
{
grad[nod]=grad[tata]+1;
inapoi[nod]=grad[nod];
for(int i=0; i<vecini[nod].size(); i++)
{
int x=vecini[nod][i];
if( x!=tata&&grad[x]==0 )
{
dfs(x,nod);
inapoi[nod]=min(inapoi[nod],inapoi[x]);
}
else if( x!=tata ) inapoi[nod]=min(inapoi[nod],grad[x]);
}
}
void dfs_solve(int nod,int tata)
{
fost[nod]=1;
stiva[++nr]=nod;
int ct=0;
for(int i=0; i<vecini[nod].size(); i++)
{
int x=vecini[nod][i];
if( fost[x]==0 )
{
ct++;
dfs_solve(x,nod);
if( grad[nod]<=inapoi[x] )
{
tr++;
while( nr>0&&stiva[nr]!=nod )
{
sol[tr].push_back(stiva[nr]);
nr--;
}
sol[tr].push_back(stiva[nr]);
}
}
}
}
int main()
{
f>>n>>m;
for(int i=1; i<=m; i++)
{
int x,y;
f>>x>>y;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
dfs(1,0);
dfs_solve(1,0);
g<<tr<<'\n';
for(int i=1; i<=tr; i++)
{
for(int j=0; j<sol[i].size(); j++)
{
g<<sol[i][j]<<' ';
}
g<<'\n';
}
}