Pagini recente » Cod sursa (job #1116172) | Cod sursa (job #2588407) | Cod sursa (job #366304) | Cod sursa (job #546707) | Cod sursa (job #2418293)
#include <bits/stdc++.h>
#define NMAX 100005
#define MMAX 200005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
vector < int > v[MMAX], sol[MMAX];
deque< int > q;
int level[NMAX], used[NMAX], low[NMAX];
int bicon;
void dfs( int k, int dad)
{
level[k] = level[dad] + 1;
low[k] = level[k];
used[k] = 1;
q.push_back(k);
for( auto x : v[k])
{
if(x == dad)continue;
if(used[x])
{
low[k] = low[k] < level[x] ? low[k] : level[x];
}
else
{
dfs(x, k);
low[k] = low[x] < low[k]? low[x] : low[k];
if( low[x] >= level[k])
{
++bicon;
int t;
do
{
t=q.back();
q.pop_back();
sol[bicon].push_back(t);
}
while(q.size()&&t!=x);
sol[bicon].push_back(k);
}
}
}
}
int main()
{
fin >>n >>m;
while ( m )
{
int x, y;
fin >>x >>y;
v[x].push_back(y);
v[y].push_back(x);
--m;
}
dfs(1,0);
fout << bicon <<"\n";
for( int i = 1; i <= bicon; ++i, fout << "\n")
for( int j = 0; j <sol[i].size(); ++j, fout<< " ")fout<<sol[i][j];
return 0;
}