Pagini recente » Cod sursa (job #594032) | Cod sursa (job #414529) | Cod sursa (job #2313246) | Cod sursa (job #2816796) | Cod sursa (job #984747)
Cod sursa(job #984747)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
const int MAX_N = 100002;
typedef struct Edge {
int x, y;
};
int N, M;
int Level[MAX_N], MinLevel[MAX_N], Father[MAX_N];
vector < int > v[MAX_N];
vector < vector < int > > BC;
stack < Edge > st;
inline bool Edge_cmp(Edge a, Edge b) {
if(a.x != b.x || a.y != b.y)
return 1;
return 0;
}
inline void DFS(int x) {
MinLevel[x] = Level[x];
for(size_t i = 0; i < v[x].size(); ++i) {
int y = v[x][i];
if(Father[y])
continue;
Father[y] = x, Level[y] = Level[x] + 1;
Edge A;
A.x = x, A.y = y;
st.push(A);
DFS(y);
if(MinLevel[y] >= Level[x]) {
vector < int > a;
while(Edge_cmp(st.top(), A) == true)
a.push_back(st.top().x), a.push_back(st.top().y), st.pop();
a.push_back(st.top().x), a.push_back(st.top().y), st.pop();
BC.push_back(a);
}
}
for(size_t i = 0; i < v[x].size(); ++i)
if(v[x][i] != Father[x])
MinLevel[x] = min(MinLevel[x], MinLevel[v[x][i]]);
}
int main() {
ifstream f("biconex.in");
ofstream g("biconex.out");
f >> N >> M;
for(int i = 1, x, y; i <= M; ++i) {
f >> x >> y;
v[x].push_back(y), v[y].push_back(x);
}
for(int i = 1; i <= N; ++i)
if(!Father[i]) {
Father[i] = i;
DFS(i);
}
g << BC.size() << "\n";
for(size_t i = 0; i < BC.size(); ++i) {
sort(BC[i].begin(), BC[i].end());
for(size_t j = 0; j < BC[i].size(); ++j)
if(j == 0 || BC[i][j] != BC[i][j-1])
g << BC[i][j] << " ";
g << "\n";
}
f.close();
g.close();
return 0;
}