Pagini recente » Cod sursa (job #1549166) | Cod sursa (job #246846) | Istoria paginii runda/er | Cod sursa (job #3260090) | Cod sursa (job #1825249)
#include <fstream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <cassert>
using namespace std;
ifstream fin ("biconex.in"); ofstream fout ("biconex.out");
typedef vector< int > graf;
const int nmax = 1e5;
const int inf = (1 << 30) - 1 + (1 << 30);
bool viz[nmax + 1];
int h[nmax + 1], d[nmax + 1], cat_de_sus[nmax + 1];
graf g[nmax + 1];
vector< vector< int > > sol;
void dfs1 (int nod, int tata) {
cat_de_sus[ nod ] = inf;
d[ nod ] = inf;
viz[ nod ] = 1;
//fout << nod << "\n";
for (auto i : g[ nod ]) {
if (i != tata) {
if (viz[ i ] == 0) {
h[ i ] = h[ nod ] + 1;
dfs1(i, nod);
d[ nod ] = min(d[ nod ], d[ i ]);
} else {
cat_de_sus[ nod ] = min(cat_de_sus[ nod ], h[ i ]);
}
}
}
d[ nod ] = min(d[ nod ], cat_de_sus[ nod ]);
}
void dfs2 (int nod, int ind) {
//assert(0 <= ind && ind < (int)sol.size());
sol[ ind ].push_back( nod );
viz[ nod ] = 1;
//fout << nod << "\n";
/*if (ind == 125000) {
exit(0);
}*/
//assert(1 <= nod && nod <= 99996);
for (auto i : g[ nod ]) {
if (viz[ i ] == 0) {
if (d[ i ] >= h[ nod ]) {
sol.push_back(vector< int > (1, nod));
dfs2(i, (int)sol.size() - 1);
} else {
dfs2(i, ind);
}
}
}
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 1; i <= m; ++ i) {
int x, y;
fin >> x >> y;
g[ x ].push_back( y );
g[ y ].push_back( x );
}
for (int i = 1; i <= n; ++ i) {
h[ i ] = inf;
}
h[ 1 ] = 0;
dfs1(1, 0);
memset(viz, 0, sizeof(viz));
sol.push_back(vector< int > ());
dfs2(1, 0);
if (sol.size() > 0 && sol[ 0 ].size() == 1) {
swap(sol[ 0 ], sol.back());
sol.pop_back();
}
fout << (int)sol.size() << "\n";
for (auto it : sol) {
for (auto it2 : it) {
fout << it2 << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}