Pagini recente » Cod sursa (job #3129712) | Cod sursa (job #265871) | Cod sursa (job #1554924) | Cod sursa (job #2213529) | Cod sursa (job #3203914)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
typedef long long ll;
const ll Nmax=1e5+5, inf=1e9+5;
int n, m, nrc;
vector <int> ad[Nmax]; //lista de adiacenta
int h[Nmax], reach[Nmax]; // inaltimea nodului in arborele dfs; inaltimea minima la care poate ajunge printr-un drum
stack <int> st; //stiva componentelor biconexe
vector <int> sol[Nmax]; //lista componentelor biconexe
void dfs(int nod, int p){
h[nod]=h[p]+1;
reach[nod]=h[nod]; // initializam nivelul minim la care putem ajunge cu nivelul curent
st.push(nod);
for (auto it:ad[nod]) // iteram prin vecinii nodului curent
if (it!=p) // daca vecinul nu este tata
if (!h[it]){ // daca fiul nu e vizitat
dfs(it, nod);
reach[nod]=min(reach[nod], reach[it]); // updatam reach-ul
if (reach[it]>=h[nod]){ // daca reach-ul fiului nu trece de inaltimea nodului avem componenta biconexa
while (st.top()!=it){
sol[nrc].pb(st.top());
st.pop();
}
sol[nrc].pb(st.top());
sol[nrc].pb(nod);
st.pop();
nrc++;
}
}
else reach[nod]=min(reach[nod], h[it]); // updatam reach-ul
}
inline void hopcraft_tarjan(){
for (int i=0; i<n; i++)
if (!h[i]) // calculam componentele biconexe pt fiecare componenta conexa
dfs(i, i);
}
int main()
{
fin>>n>>m;
int a, b;
for (int i=0; i<m; i++){
fin>>a>>b;
a--; b--; // indexam nodurile de la 0
ad[a].pb(b);
ad[b].pb(a);
}
hopcraft_tarjan();
fout<<nrc<<'\n';
for (int i=0; i<nrc; i++){ // afisam componentele biconexe
for (auto it:sol[i])
fout<<it+1<<' ';
fout<<'\n';
}
return 0;
}