Pagini recente » Cod sursa (job #775179) | Cod sursa (job #2398426) | Cod sursa (job #1751501) | Cod sursa (job #2729172) | Cod sursa (job #1165419)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX = 101101;
#define x first
#define y second
int N, M;
int Level[MAX], Highest[MAX];
bool viz[MAX];
vector<int> V, G[MAX];
vector< pair<int, int> > Edges;
vector< vector<int> > BC;
void citire() {
ifstream in("biconex.in");
in >> N >> M;
for(int i = 1, A, B; i <= M; i++) {
in >> A >> B;
G[A].push_back(B);
G[B].push_back(A);
} in.close();
}
void dfs(int nod, int Dad, int Nivel) {
//cerr << "Entered dfs for node " << nod << "\n";
viz[nod] = true;
Level[nod] = Highest[nod] = Nivel;
for(size_t i = 0; i < G[nod].size(); i++) {
int dest = G[nod][i];
//cerr << "Dest is " << dest << "\n";
if(dest == Dad) continue;
if(!viz[dest]) {
//cerr << "Added " << nod << " " << dest << " to edges\n";
Edges.push_back(make_pair(nod, dest));
dfs(dest, nod, Nivel + 1);
Highest[nod] = min(Highest[nod], Highest[dest]);
} else {
Highest[nod] = min(Highest[nod], Level[dest]);
continue;
}
if(Highest[dest] >= Level[nod]) {
//cerr << "We are in node " << nod << " and we are trying to delete\n";
V.clear();
int A, B;
do {
A = Edges.back().x, B = Edges.back().y;
//cerr << "Popped " << A << " " << B << " from edges\n";
Edges.pop_back();
V.push_back(A);
V.push_back(B);
} while(!V.empty() && nod != A && dest != B);
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
BC.push_back(V);
}
}
//cerr << "Exiting dfs for node " << nod << "\n";
}
void solve() {
for(int i = 1; i <= N; i++) {
if(!viz[i])
dfs(i, 0, 1);
}
}
void afisare() {
ofstream out("biconex.out");
out << BC.size() << "\n";
for(size_t i = 0; i < BC.size(); i++) {
for(size_t j = 0; j < BC[i].size(); j++)
out << BC[i][j] << " ";
out << "\n";
}
}
int main() {
citire();
solve();
afisare();
}