Pagini recente » Cod sursa (job #1079532) | Cod sursa (job #2613271) | Cod sursa (job #1805652) | Cod sursa (job #2760166) | Cod sursa (job #1361049)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream F("biconex.in");
ofstream G("biconex.out");
const int N = 100010;
int n,m,lvl[N],bestlvl[N],mk[N],ans;
vector<int> v[N],s1,s2,sol[N];
void dfs(int x,int dd)
{
lvl[x] = lvl[dd] + 1;
bestlvl[x] = lvl[x];
for (int i=0;i<int(v[x].size());++i)
{
int y = v[x][i];
if ( lvl[y] == 0 )
{
s1.push_back(x);
s2.push_back(y);
dfs(y,x);
bestlvl[x] = min(bestlvl[x],bestlvl[y]);
if ( bestlvl[y] >= lvl[x] )
{
++ans;
if ( !s1.empty() )
while ( 1 )
{
int ok = ( s1.back()!=x || s2.back()!=y );
if ( mk[s1.back()] != ans ) mk[s1.back()] = ans, sol[ans].push_back( s1.back() );
if ( mk[s2.back()] != ans ) mk[s2.back()] = ans, sol[ans].push_back( s2.back() );
s1.pop_back(), s2.pop_back();
if ( !ok ) break;
if ( s1.empty() ) break;
}
}
}
else
if ( y != dd )
bestlvl[x] = min(bestlvl[x],lvl[y]);
}
}
int main()
{
F>>n>>m;
for (int i=1,x,y;i<=m;++i)
{
F>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
G<<ans<<'\n';
for (int i=1;i<=ans;++i)
{
for (int j=0;j<int(sol[i].size());++j)
G<<sol[i][j]<<' ';
G<<'\n';
}
}