Pagini recente » Cod sursa (job #452791) | Cod sursa (job #2798527)
#include <iostream>
#include <fstream>
#include <vector>
#define MAX 100001
using namespace std;
ifstream fin ("biconex.in");
ofstream fout("biconex.out");
vector <int> compBiconexe[MAX];
class Graf{
public:
//date membre
vector <int> A[MAX]; //liste de adiacenta
int mM, mN;
int nrComp; //nr comp conexe
static bool viz[MAX];
static int up[MAX];
static int nivel[MAX];
static int S[MAX];
static int top;
int nrCompBiconexe;
//constructor
Graf(int N, int M){
mN = N;
mM = M;
nrComp = 0;
nrCompBiconexe = 0;
}
void CitireGOrientat(){
int x, y;
for(int i = 1; i <= mM; i++){
// citim muchiile
fin >> x >> y;
A[x].push_back(y); //adaugam ambele noduri in lista celuilalt de adiacenta
A[y].push_back(x); //deoarece graful e neorientat
}
}
void DFS(int start);
void ComponenteConexe();
void DFS_Biconex(int start, int father);
void AfisareBiconex();
};
bool Graf :: viz[MAX] ={0};
int Graf :: up[MAX] = {0};
int Graf :: nivel[MAX] = {0};
int Graf :: S[MAX] = {0};
int Graf :: top = 0;
void Graf :: DFS (int start){
viz[start] = 1;
// vizitam nodul din care plecam
for(int i = 0; i < A[start].size(); i++){
// parcurgem toti vecinii nodului start
if(!viz[A[start][i]] ){
// daca nu am mai vizitat acest vecin
DFS(A[start][i]);
}
}
}
void Graf :: ComponenteConexe(){
for(int i = 1; i <= mN; i++){
if(!viz[i]){
nrComp++;
DFS(i);
}
}
}
void Graf :: DFS_Biconex(int start, int father){
viz[start] = 1;
// vizitam nodul din care plecam
up[start] = nivel[start];
S[++top] = start;
for(int i = 0; i < A[start].size(); i++){
// parcurgem toti vecinii nodului start
if(i != father ){
//daca nu e nodul din care am venit
if(viz[A[start][i]]){
// daca am mai vizitat acest vecin
up[start] = min(up[start], nivel[A[start][i]]);
}
else{
//daca nu a mai fost vizitat
nivel[A[start][i]] = nivel[start] +1;
DFS_Biconex(A[start][i], start);
if(up[A[start][i]] >= nivel[start]){
nrCompBiconexe++;
while(top && S[top] != A[start][i]){
compBiconexe[nrCompBiconexe].push_back(S[top--]);
}
compBiconexe[nrCompBiconexe].push_back(S[top--]);
compBiconexe[nrCompBiconexe].push_back(start);
}
up[start] = min(up[start], up[A[start][i]]);
}
}
}
}
void Graf :: AfisareBiconex()
{
fout << nrCompBiconexe << "\n";
for ( int i = 1; i <= nrCompBiconexe; i++ ){
for ( int j = 0; j < compBiconexe[i].size(); j++ )
fout << compBiconexe[i][j] << " ";
fout << "\n";
}
}
int main(){
int N, M;
fin >> N >> M;
Graf G(N,M);
G.CitireGOrientat();
G.DFS_Biconex(1,0);
G.AfisareBiconex();
return 0;
}