Pagini recente » Cod sursa (job #180893) | Cod sursa (job #1690977) | Cod sursa (job #3149113) | Cod sursa (job #1290199) | Cod sursa (job #2143979)
#include <fstream>
#include <vector>
#include <set>
#define nmax 100005
#define mmax 200005
using namespace std;
fstream f1("biconex.in", ios::in);
fstream f2("biconex.out", ios::out);
int n, m, nrcomp, low[nmax], dfn[nmax], vf;
vector <int> v[nmax];
set <int> s[nmax];
struct stivaaa
{
int x, y;
}stiva[mmax];
void citire()
{
int i, x, y;
f1>>n>>m;
for(i=1; i<=m; i++)
{
f1>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(i=1; i<=n; i++) dfn[i]=-1;
}
void comp_biconexa(int x, int y)
{
nrcomp++;
while((vf>0)&&((x!=stiva[vf].x)||(y!=stiva[vf].y)))
{
s[nrcomp].insert(stiva[vf].x); s[nrcomp].insert(stiva[vf].y);
vf--;
}
s[nrcomp].insert(x); s[nrcomp].insert(y);
vf--;
}
void dfs(int nod, int tata, int niv)
{
int vec;
low[nod]=dfn[nod]=niv;
for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
if((*it)!= tata)
{
vec=*it;
if(dfn[vec]!=-1) ///deja a fost vizitat, deci [nod, vec] muchie de intoarcere
low[nod]=min(low[nod], dfn[vec]);
else ///fiu nevizitat
{
vf++; stiva[vf].x=nod; stiva[vf].y=vec;///pui muchie din arbore (ai maxim 1 muchie de intoarcere pe care nu o mai pui)
dfs(vec, nod, niv+1);
low[nod]=min(low[nod], low[vec]);
if(low[vec]>= dfn[nod]) comp_biconexa(nod, vec);///nod=pct art., scoti muchiile din comp. biconexa respectiva
}
}
}
void afisare()
{
int i;
f2<<nrcomp<<"\n";
for(i=1; i<=nrcomp; i++)
{
for(auto it=s[i].begin(); it!=s[i].end(); ++it)
f2<<(*it)<<' ';
f2<<"\n";
}
}
int main()
{
citire();
dfs(1, 0, 1);
afisare();
return 0;
}