Pagini recente » Cod sursa (job #249419) | Cod sursa (job #2886748) | Cod sursa (job #2162530) | Cod sursa (job #1339530) | Cod sursa (job #2144011)
#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, vf, lista[mmax], cap[nmax], poz;
vector <int> v[nmax], low, dfn;
set <int> s;
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);
}
low.resize(n+2);
dfn.resize(n+2);
for(i=1; i<=n; i++) dfn[i]=-1;
}
void comp_biconexa(int x, int y)
{
int i;
s.clear();
while((vf>0)&&((x!=stiva[vf].x)||(y!=stiva[vf].y)))
{
s.insert(stiva[vf].x); s.insert(stiva[vf].y);
vf--;
}
s.insert(x); s.insert(y);
vf--;
nrcomp++;
i= cap[nrcomp]=poz+1;
for(auto it=s.begin(); it!=s.end(); ++it)
{
lista[i]=*it;
i++;
}
poz=i-1;
cap[nrcomp+1]=poz+1;
}
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, j;
f2<<nrcomp<<"\n";
for(i=1; i<=nrcomp; i++)
{
for(j=cap[i]; j<cap[i+1]; j++)
f2<<lista[j]<<' ';
f2<<"\n";
}
}
int main()
{
citire();
dfs(1, 0, 1);
afisare();
return 0;
}