Pagini recente » Cod sursa (job #1416103) | Cod sursa (job #1573110) | Cod sursa (job #2970681) | Cod sursa (job #3130121) | Cod sursa (job #2501351)
#include <fstream>
#include<iostream>
#include<stack>
#include<bits/stdc++.h>
using namespace std;
#define NMAX 100005
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int minim(int x,int y)
{
if(x<y) return x;
else return y;
}
vector <int> v[NMAX];
int dfs[NMAX],low[NMAX];
int vfs;
int nrdfs;
int nr;
int n,m;
vector<int> solutie[NMAX];
int viz[NMAX];
struct muchie
{
int f,t;
};
muchie S[NMAX];
void citeste()
{
fin>>n>>m;
int x,y;
for(int i=1;i<=m;i++)
{
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++)
dfs[i] = low[i] = -1;
S[0].f = 1;
S[0].t = -1;
vfs=0;
nrdfs=0;
}
void afisare(int x,int u)
{
muchie p;
nr++;
do
{
p = S[vfs--];
if(viz[p.f] != nr)
{
viz[p.f] = nr;
solutie[nr].push_back(p.f);
}
if(viz[p.t] != nr)
{
viz[p.t] = nr;
solutie[nr].push_back(p.t);
}
}while(p.f !=x || p.t != u);
}
void biconexe(int u,int tu)
{
int x,p;
dfs[u] = low[u] = ++nrdfs;
for(p = 0 ;p<v[u].size();p++)
{
x = v[u][p];
if(x!=tu && dfs[x] < dfs[u])
{
S[++vfs].f = x;
S[vfs].t = u;
}
if(dfs[x] == -1)
{
biconexe(x,u);
low[u] = minim(low[u],low[x]);
if(low[x] >= dfs[u])
{
afisare(x,u);
}
}
else
{
low[u] = minim(low[u],dfs[x]);
}
}
}
int main()
{
citeste();
biconexe(1,-1);
fout<<nr<<'\n';
for(int i=1;i<=nr;i++)
{
sort(solutie[i].begin(),solutie[i].end());
for(int j=0;j<solutie[i].size();j++)
fout<<solutie[i][j]<<" ";
fout<<'\n';
}
return 0;
}