Pagini recente » Cod sursa (job #375984) | Cod sursa (job #1130665) | Cod sursa (job #1731573) | Cod sursa (job #1807838) | Cod sursa (job #3196413)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int nmax = 1e5 +7;
vector<int> g[nmax];
int depth[nmax],viz[nmax],low[nmax];
int rad = 1;
void dfs_depth(int nod, int tata, int adancime)
{
depth[nod] = adancime;
viz[nod] = 1;
for(auto vecin: g[nod])
{
if(vecin == tata || viz[vecin]) continue;
dfs_depth(vecin, nod, adancime + 1);
}
}
void dfs_low(int nod, int tata)
{
low[nod] = depth[nod];
for(auto vecin: g[nod]) //muchie verde
{
if(vecin == tata || depth[vecin] == depth[nod] + 1) continue;
//am dat de o muchie de intoarcere!
low[nod] = min(low[nod], depth[vecin]);
}
for(auto vecin: g[nod]) //muchie rosie
{
if(depth[vecin] != depth[nod] + 1) continue;
dfs_low(vecin, nod);
low[nod] = min(low[nod], low[vecin]);
}
}
vector<int> critice;
void dfs_critice(int nod)
{
bool e_critic = 0;
int nr_fii = 0;
for(auto vecin: g[nod])
{
if(depth[vecin] == depth[nod] + 1)
{
nr_fii++;
dfs_critice(vecin);
}
if(low[vecin] >= depth[nod]) //nu reusesc sa urc mai sus de nod
{
e_critic = 1;
}
}
if(nod == rad && nr_fii >= 2) e_critic = 1; //daca radacina are mai mult de 2 fii
if(e_critic) critice.push_back(nod);
}
vector<pair<int,int> > poduri;
void dfs_poduri(int nod)
{
for(auto vecin: g[nod])
{
if(depth[vecin] == depth[nod] + 1)
{
if(low[vecin] > depth[nod]) //nu reusesc nici macar sa ma intorc la nod
{
poduri.push_back({nod,vecin});
}
dfs_poduri(vecin);
}
}
}
stack<int> dfs_stack;
vector<vector<int> > biconexe;
void dfs_biconexe(int nod)
{
dfs_stack.push(nod);
for(auto vecin: g[nod])
{
if(depth[vecin] == depth[nod] + 1)
{
dfs_biconexe(vecin);
if(low[vecin] >= depth[nod]) //nu reusesc sa ma intorc mai sus
{ //deci am ceva ciclu chiar sub nodul meu
//am gasit o componenta biconexa
vector<int> comp_biconexa;
while(dfs_stack.top() != vecin)
{
comp_biconexa.push_back(dfs_stack.top());
dfs_stack.pop();
}
comp_biconexa.push_back(vecin);
comp_biconexa.push_back(nod);
dfs_stack.pop();
biconexe.push_back(comp_biconexa);
}
}
}
}
int main()
{
int n,m; fin>>n>>m;
for(int i=1; i<=m; i++)
{
int x,y; fin>>x>>y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs_depth(rad,0,1);
dfs_low(rad,0);
dfs_critice(rad);
dfs_poduri(rad);
dfs_biconexe(rad);
fout<<biconexe.size()<<"\n";
for(auto comp_biconexa : biconexe)
{
sort(comp_biconexa.begin(), comp_biconexa.end());
for(auto nod: comp_biconexa)
{
fout<<nod<<" ";
}
fout<<"\n";
}
return 0;
}