Pagini recente » Cod sursa (job #372971) | Cod sursa (job #2494750) | Cod sursa (job #1131773) | Cod sursa (job #2914352) | Cod sursa (job #2798536)
#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; // adaugam startul in stiva
for ( auto i : A[start] ){
// parcurgem toti vecinii nodului start
if ( i == father ) continue;
//daca nu e nodul din care am venit
if ( viz[i] ){
// daca am mai vizitat acest vecin
up[start] = min(up[start], nivel[i]);
}
else{
nivel[i] = nivel[start] + 1;
DFS_Biconex(i, start);
if ( up[i] >= nivel[start] ){
nrCompBiconexe++;
while ( top && S[top] != i ){
compBiconexe[nrCompBiconexe].push_back(S[top--]);
}
compBiconexe[nrCompBiconexe].push_back(S[top--]);
compBiconexe[nrCompBiconexe].push_back(start);
}
up[start] = min(up[start], up[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;
}