Pagini recente » Cod sursa (job #324800) | Cod sursa (job #1033647) | Monitorul de evaluare | Cod sursa (job #1145028) | Cod sursa (job #2376600)
#include <algorithm>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
#define FILE_NAME "biconex"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");
const int MAX_NODES = 100000 + 4;
const int MAX_EDGES = 200000 + 4;
vector < int > G[MAX_NODES];
vector < vector < int > > CB;
vector < int > Level, Return;
stack < pair < int, int > > Stiva;
int N, M;
void add_compbiconexa(int x, int y)
{
vector < int > compBiconexa;
int tx, ty;
do
{
tx = Stiva.top().first, ty = Stiva.top().second;
Stiva.pop();
compBiconexa.push_back(tx);
compBiconexa.push_back(ty);
} while(tx != x || ty != y);
CB.push_back(compBiconexa);
}
void compute_compbiconexe(int nod, int father, int lvl)
{
Return[nod] = Level[nod] = lvl;
for(auto next = G[nod].cbegin(), fin = G[nod].cend(); next != fin; ++next)
{
if(*next != father)
{
if(Level[*next] == -1)
{
Stiva.push(make_pair(nod, *next));
compute_compbiconexe(*next, nod, lvl + 1);
Return[nod] = min(Return[nod], Return[*next]);
if(Return[*next] >= Level[nod])
add_compbiconexa(nod, *next);
}
else
Return[nod] = min(Return[nod], Level[*next]);
}
}
}
void read_input()
{
in >> N >> M;
while(M--)
{
int x, y;
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
Level.resize(N+1), Return.resize(N+1);
Level.assign(N+1, -1);
}
int main()
{
read_input();
compute_compbiconexe(1, 0, 0);
out << CB.size() << '\n';
for(auto it = CB.begin(), fin = CB.end(); it != fin; ++it)
{
sort(it->begin(), it->end());
it->erase(unique(it->begin(), it->end()), it->end());
for(auto zit = it->cbegin(), zfin = it->cend(); zit != zfin; ++zit)
out << *zit << ' ';
out << '\n';
}
return 0;
}