Pagini recente » Cod sursa (job #2266587) | Cod sursa (job #2131173) | Cod sursa (job #2698391) | Cod sursa (job #753861) | Cod sursa (job #728803)
Cod sursa(job #728803)
#include<cstdio>
#include<bitset>
#include<vector>
#define dim 8192
using namespace std;
int i,j,n,m,nv[100024],t[100024],l[100024],st[100024],pz;
char c[dim+3];
vector<int> a[100024];
bitset<100024> fol;
vector< vector<int> > rez;
inline void cit(int &x)
{
x=0;
while(c[pz]<'0'||c[pz]>'9')
if(++pz==dim) fread(c,dim,1,stdin),pz=0;
while(c[pz]>='0'&&c[pz]<='9')
{
x=x*10+c[pz]-'0';
if(++pz==dim) fread(c,dim,1,stdin),pz=0;
}
}
void scoate(int i)
{
vector<int> inter;
while(st[0]>0)
{
inter.push_back(st[st[0]]);
st[0]--;
}
inter.push_back(i);
rez.push_back(inter);
}
void dfs(int i)
{
fol[i]=1;
l[i]=nv[i];
for(int j=0;j<a[i].size();++j)
{
int fiu=a[i][j];
if(!fol[fiu])
{
t[fiu]=i;
nv[fiu]=nv[i]+1;
dfs(fiu);
if(l[i]>l[fiu]) l[i]=l[fiu];
if(l[fiu]>=nv[i]) scoate(i);
}
else if(fiu!=t[i]&&l[i]>nv[fiu])
l[i]=nv[fiu];
}
st[++st[0]]=i;
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
cit(n);
cit(m);
for(i=1;i<=m;++i)
{
int x=0,y=0;
cit(x);
cit(y);
a[x].push_back(y);
a[y].push_back(x);
}
for(i=1;i<=n;++i)
if(!fol[i])
{
nv[i]=1;
dfs(i);
}
printf("%d\n",rez.size());
for(i=0;i<rez.size();++i)
{
for(j=0;j<rez[i].size();++j) printf("%d ",rez[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}