Pagini recente » Cod sursa (job #1489799) | Cod sursa (job #1385092) | Cod sursa (job #2020984) | Cod sursa (job #1925348) | Cod sursa (job #2796546)
#include<iostream>
#include<fstream>
#include<queue>
#include<stack>
#include<vector>
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
class graf{
public:
//bfs - declarari
//int N, M, S, vizitat[100010], minime[100010];
//vector<int> stocare[100010];
//queue<pair<int, int>> coada;
//dfs - declarari
// int N, M;
//vector<vector<int>> D;
//vector<int>ok; //pt a marca nodul ca vizitat sau nu - 0 sau 1
// graf(){}
//BFS
// void bfs(int start)
// {
// pair<int, int> curent;
// coada.push({start, 0}); // dist de la start la el insusi e 0
// minime[start] = 0; // momentan, minime va avea val 0
// vizitat[start] = 1; // vizitez nodul curent
//while(!coada.empty())
//{
// curent = coada.front();
// minime[curent.first] = curent.second;
// coada.pop();
// for(auto i : stocare[curent.first]) // parcurgem primele elem din pereche
// if(!vizitat[i]){
// coada.push({i, curent.second+1}); //cresc contorul
// vizitat[i] = 1; // vizitez nodul i
// }
// }
// }
// void creare_graf(int N, int M, int S)
// {
// this-> N = N;
// this-> M = M;
// this-> S = S;
// for(int i = 0; i< 100010; i++)
// minime[i] = -1; //umplem tabl de dist minime cu -1
// }
// void creare_adiacente(int M)
//{
// int nod1, nod2;
// for(int i = 1; i<= M; i++)
// {
// f>>nod1>>nod2;
// stocare[nod1].push_back(nod2);
// }
// }
//
//DFS
/*
void dfs(int start)
{
ok[start] = 1;
for(auto i: D[start]) // parcurg D
if(ok[i]==0)
{
ok[i] =1;
dfs(i);
}
}
void creare_graf_Dfs(int N, int M)
{
this-> N = N;
this -> M =M;
ok=vector<int>(N+1);
D=vector<vector<int>>(N+1);
}
void creare_adiacente_Dfs(int M)
{
int nod1, nod2;
for(int i = 1; i<= M; i++)
{
f>>nod1>>nod2;
D[nod1].push_back(nod2);
D[nod2].push_back(nod1);
}
}
int comp_conexe(int N)
{
int k= 0;
for(int i =1; i<= N; i++)
if(ok[i]==0)
{
k++;
dfs(i);
}
return k;
}
*/
//biconex declarari
int N, M, z, d[100001], l[100001];
stack<pair<int, int>> st; //stiva fol first si second
vector<vector<int>> D;
vector<vector<int>> rez; //vectorul pt rezultate biconex
//graf(){}
void bic(int x, int y)
{
vector<int>vect;
while(st.top().first!=x && st.top().second!=y) //parcurg cat timp first e dif de nod1 si second e dif de nod2
{
vect.push_back(st.top().second); //retinem in vect nodul in care aj
st.pop(); // in scoatem din stiva
}
vect.push_back(y); //adaugam nod2 in vect
vect.push_back(x); //adaug nod1 in vect
st.pop(); //scoatem din stiva ultimul nod ramas
rez.push_back(vect); //tin minte nodurile marcate din vect cu aj lui rez
}
void dfsbic(int nod_curent)
{
d[nod_curent]=++z;
l[nod_curent]=z;
for(auto iter: D[nod_curent])
{
if(d[nod_curent]!=0)
{
l[nod_curent] = min(d[iter], l[nod_curent]) ; //pastram minimul
}
else
{
st.push({nod_curent, iter}); //adaug ca pereche in stiva nodul curent i si unde am ajuns cu unde am ajuns cu iteratorul
dfsbic(iter); //apelam recursiv dfsbic pt fiecare nod nemarcat
l[nod_curent]=min(l[nod_curent], l[iter]);
if(d[nod_curent]<=l[iter]) bic(nod_curent, iter);
}
}
}
void creare_graf_bic(int N, int M)
{
this-> N = N;
this -> M =M;
rez=vector<vector<int>>(N+1);
D=vector<vector<int>>(N+1);
}
void creare_adiacente_bic(int M)
{
int nod1, nod2;
for(int i = 1; i<= M; i++)
{
f>>nod1>>nod2;
D[nod1].push_back(nod2);
D[nod2].push_back(nod1);
}
}
};
graf Gr;
int main()
{
//BFS
//int N, M, S;
//f>>N>>M>>S;
//Gr.creare_graf(N, M, S);
// Gr.creare_adiacente(M);
//Gr.bfs(S);
//for(int i = 1; i<=N; i++)
// g<< Gr.minime[i]<<" ";
//DFS
//int N, M;
// f>>N>>M;
//Gr.creare_graf_Dfs(N, M);
//Gr.creare_adiacente_Dfs(M);
//g<<Gr.comp_conexe(N);
//Comp Biconexe
int N, M;
f>>N>>M;
Gr.creare_graf_bic(N, M);
Gr.creare_adiacente_bic(M);
Gr.dfsbic(1);
g<<Gr.rez.size()<<endl;
for(int i=0; i<Gr.rez.size(); i++)
{
for(int j=0; j<Gr.rez.size(); j++)
g<<Gr.rez[i][j]<<" ";
g<<endl;
}
return 0;
}