Pagini recente » Cod sursa (job #1318012) | Cod sursa (job #565219) | Cod sursa (job #3145754) | Cod sursa (job #2287027) | Cod sursa (job #3262864)
/*
____ ___ _ ___ ____ _
/ ___| / _ \| | |_ _/ ___| / \
\___ \| | | | | | | | / _ \
___) | |_| | |___ | | |___ / ___ \
|____/ \___/|_____|___\____/_/ \_\
*/
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long int
#define pii pair<int,int>
const int NMAX = 2e5+9;
const int MOD = 1e9+7;
int binpow(int n, int k)
{
if (k==0)
{
return 1;
}
int x=binpow(n,k/2)%MOD;
if (k%2==0)
{
return x*x%MOD;
}
else
{
return x*x%MOD*n%MOD;
}
}
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
#define cin fin
#define cout fout
vector<int>g[NMAX],comp[NMAX];
int n,m,i,j,bcc;
stack<int>s;/// folosesc o stiva pentru determinarea componentelor biconexe
/// daca la un moment dat am gasit nodul node ca fiind puncte de articulatie, golesc stiva pana la it inclusiv, aceste noduri impreuna cu node formand o componenta biconexa
int nma[NMAX];/// nivelul minim accesibil dintr-un nod x prin muchii din arborele dfs si dupa printr-o muchie de intoarcere
int depth[NMAX];//depth-ul nodului x in dfs tree
bool viz[NMAX];
void dfs (int node, int parent=0)
{
viz[node]=1;
nma[node]=depth[node]=depth[parent]+1;///se initializeaza cu depth-ul nodului curent
s.push (node);
for (auto it : g[node])
{
if (viz[it])
{
nma[node]=min(nma[node],depth[it]);/// cazul in care ma intorc
}
else
{
dfs(it,node);
nma[node]=min(nma[node],nma[it]);
if (nma[it]>=depth[node])/// node este punct de articulatie
{
bcc++;
while (!s.empty () && s.top()!=it)
{
comp[bcc].pb(s.top());
s.pop();
}
comp[bcc].pb(s.top());
s.pop();
comp[bcc].pb(node);
}
}
}
}
void run_case ()
{
cin>>n>>m;
for (i=1; i<=m; i++)
{
int a,b;
cin>>a>>b;
g[a].pb(b),g[b].pb(a);
}
dfs(1);
cout<<bcc<<'\n';
for (i=1; i<=bcc; i++)
{
sort (comp[i].begin(),comp[i].end());
for (auto nod : comp[i])
{
cout<<nod<<' ';
}
cout<<'\n';
}
}
signed main ()
{
ios_base::sync_with_stdio(0);
cin.tie(NULL),cout.tie ();
int teste=1;
while (teste--)
{
run_case();
}
}