Pagini recente » Cod sursa (job #2440272) | Cod sursa (job #2343847) | Cod sursa (job #342550) | Cod sursa (job #3290317) | Cod sursa (job #2176581)
#include<bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMAX = 100000;
template <size_t template_size>
struct Biconexe
{
/// takes an undirected graph (with both (x,y) (y,x) edges included)
/// and returns a list of connected component an a per CRITICAL NODE basis
static const int NMAX = ::NMAX; /// compile time yea bois
stack<pair<int,int>> stk;
vector<vector<int>> comps;
vector<int> G[NMAX+2];
bool viz[NMAX+2];
int niv[NMAX+2], low[NMAX+2];
Biconexe(vector<int> (&g)[NMAX+2])
{
for( int i = 1; i <= NMAX; ++i ) G[i] = g[i];
}
void another_component(int x, int y)
{
int lx, ly;
vector<int> comp;
do {
lx = stk.top().first; ly = stk.top().second;
comp.push_back(ly);
stk.pop();
} while( !(x == lx && y == ly) );
comp.push_back(x);
comps.push_back(comp);
}
void dfs(int nod, int tata = -1, int time = 1)
{
viz[nod] = 1;
niv[nod] = low[nod] = time;
for( int& x : G[nod] ) {
if( !viz[x] ) {
stk.push({nod, x});
dfs(x, nod, time + 1);
low[nod] = min(low[nod], low[x]);
if( low[x] >= niv[nod] )
another_component(nod, x);
}
else {
low[nod] = min(low[nod], niv[x]);
}
}
}
vector<vector<int>> getBiconexe()
{
memset(viz, 0, sizeof(viz));
for( int i = 1; i <= NMAX; ++i ) if( !viz[i] )
dfs(i);
return comps;
}
};
int main()
{
vector<int> G[NMAX+2];
int N, M;
in >> N >> M;
for( int i = 1; i <= M; ++i ) {
int x,y;
in >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
Biconexe<NMAX> CB(G);
auto bicone = CB.getBiconexe();
out << bicone.size()<< '\n';
for( auto & ln : bicone ) {
for( const auto & x : ln ) out << x << ' ';
out << '\n';
}
return 0;
}