Pagini recente » Cod sursa (job #2262357) | Cod sursa (job #1166768) | Cod sursa (job #3238147) | Cod sursa (job #1728561) | Cod sursa (job #3152324)
#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 lvl[Nmax];
bool vis[Nmax];
stack <int> st; //stiva componentelor biconexe
vector <int> sol[Nmax]; //lista componentelor biconexe
int dfs(int nod, int p){
if (vis[nod]) ///daca am trecut deja prin nod returnam nivelul
return lvl[nod];
vis[nod]=1;
lvl[nod]=lvl[p]+1;
st.push(nod);
int mn=lvl[nod]; ///initializam nivelul minim la care putem ajunge cu nivelul curent
for (auto it:ad[nod]){ ///iteram prin vecinii nodului curent
int crt;
bool ok=vis[it];
if (it!=p){ ///daca vecinul nu este tata
crt=dfs(it, nod); ///atunci updatam minimul curent
mn=min(mn, crt);
if (!ok && crt>=lvl[nod]){ ///daca vecinul nu este vizitat si nivelul minim al sau este mai mare sau egal cu cel curent
while (st.top()!=it){ /// atunci se initializeaza o noua componenta biconexa
sol[nrc].pb(st.top());
st.pop();
}
sol[nrc].pb(st.top());
sol[nrc].pb(nod);
st.pop();
nrc++;
}
}
}
return mn; ///returnam nivelul minim la care se poate ajunge pornind din nodul curent
}
inline void hopcraft_tarjan(){
lvl[n]=-1;
for (int i=0; i<n; i++)
if (!vis[i]) ///calculam componentele biconexe pt fiecare componenta conexa
dfs(i, n);
}
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;
}