Pagini recente » Cod sursa (job #3211425) | Cod sursa (job #1478805) | Cod sursa (job #2835923) | Cod sursa (job #2199183) | Cod sursa (job #1822803)
#include<fstream>
#include<vector>
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], comp[nmax + 1];
bool super_critic[nmax + 1];
int nrc;
graf g[nmax + 1];
vector< int > aux;
vector< vector< int > > sol;
void dfs1 (int nod, int tata) {
cat_de_sus[ nod ] = inf;
d[ nod ] = inf;
int cate_sus = 0;
for (auto i : g[ nod ]) {
if (i != tata) {
if (h[ i ] == inf) {
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 ]);
}
}
cate_sus += (h[ i ] < h[ nod ]);
}
if (d[ nod ] >= h[ nod ] && cate_sus <= 1) {
super_critic[ nod ] = 1;
}
d[ nod ] = min(d[ nod ], cat_de_sus[ nod ]);
}
void dfs2 (int nod) {
aux.push_back( nod );
viz[ nod ] = 1;
comp[ nod ] = nrc;
for (auto i : g[ nod ]) {
if (viz[ i ] == 0 && super_critic[ i ] == 0 && h[ i ] > h[ nod ]) {
dfs2( i );
}
}
}
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);
for (int i = 1; i <= n; ++ i) {
if (super_critic[ i ] == 1) {
aux.clear();
dfs2( i );
++ nrc;
if (aux.size() > 1) {
sol.push_back( aux );
}
}
}
for (int i = 1; i <= n; ++ i) {
for (auto j : g[ i ]) {
if (comp[ j ] != comp[ i ] && i < j) {
aux.clear();
aux.push_back( i ); aux.push_back( j );
sol.push_back( aux );
}
}
}
fout << (int)sol.size() << "\n";
for (auto it : sol) {
for (auto it2 : it) {
fout << it2 << " ";
}
fout << "\n";
}
fin.close();
fout.close();
return 0;
}