Pagini recente » Cod sursa (job #2037930) | Cod sursa (job #2379829) | Cod sursa (job #689625) | Cod sursa (job #3251198) | Cod sursa (job #1430797)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <vector>
#include <sstream>
#include <bitset>
#define NMAX 100001
#define mkedge(a,b) make_pair(a,b)
#define min(a,b) ((a)<(b))?(a):(b)
typedef std::pair<int, int> edge;
const char IN[] = "biconex.in", OUT[] = "biconex.out";
using namespace std;
vector<int> G[NMAX];
int N, M;
inline void readData() {
freopen(IN, "r", stdin);
scanf("%d %d", &N, &M);
for (int m = 0; m < M; ++m) {
int s, d;
scanf("%d %d", &s, &d);
G[s].push_back(d);
G[d].push_back(s);
}
fclose(stdin);
}
int discovery_time;
stack<edge> s;
int disc_time[NMAX], lowlink[NMAX];
std::ostringstream out;
int nrbc;
inline void pop_biconex(int const u, int const v) {
edge e;
edge check = mkedge(u, v);
bitset<NMAX> added;
do {
e = s.top(); s.pop();
if (!added[e.first]) {
out << e.first << " "; added[e.first].flip();
}
if (!added[e.second]){
out << e.second << " "; added[e.second].flip();
}
} while (check != e);
out << endl;
++nrbc;
}
inline void DFS_biconex(int node, int const father){
disc_time[node] = lowlink[node] = ++discovery_time;
for (auto &n : G[node]) {
if (n == father) continue;
if (!disc_time[n]) {
s.push(mkedge(node, n));
DFS_biconex(n, node);
lowlink[node] = min(lowlink[node], lowlink[n]);
if (lowlink[n] >= disc_time[node]) {
//punct de articulatie
//se poate ajunge la un nod stramos in DFS printr-un copil
pop_biconex(node, n);
}
}
else lowlink[node] = min(lowlink[node], disc_time[n]);
}
}
int main() {
readData();
for (int i = 1; i <= N; ++i)
if (!disc_time[i]) DFS_biconex(i, 0);
freopen(OUT, "w", stdout);
cout << nrbc << endl << out.str();
fclose(stdout);
return 0;
}