Pagini recente » Cod sursa (job #399249) | Cod sursa (job #2268374) | Cod sursa (job #2378098) | Cod sursa (job #417703) | Cod sursa (job #1379026)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
FILE* in=fopen("biconex.in","r");
FILE* out=fopen("biconex.out","w");
const int Q=100007,W=200007;
int lst[Q],val[2*W],nxt[2*W],nr;
void add(int a, int b)
{
val[++nr]=b;
nxt[nr]=lst[a];
lst[a]=nr;
}
int n,m;
int viz[Q];
int h[Q];
std::stack<int> s;
std::vector<int> comp[Q];
int up[Q];
int c[2*W];
int nrcomp;
void dfs(int nod)
{
viz[nod]=1;
for(int p=lst[nod]; p; p=nxt[p])
{
if(viz[val[p]]==0)
{
s.push(p);
h[val[p]]=h[nod]+1;
dfs(val[p]);
if(up[val[p]]==nod)
{
nrcomp++;
while(s.top()!=p)
{
c[s.top()]=nrcomp;
s.pop();
}
c[s.top()]=nrcomp;
s.pop();
}
if(h[up[val[p]]] < h[up[nod]])
up[nod]=up[val[p]];
}
if(viz[val[p]]==1)
{
if(h[val[p]] < h[up[nod]])
{
up[nod]=val[p];
}
}
}
viz[nod]=2;
}
int main()
{
fscanf(in,"%d%d",&n,&m);
int a,b;
for(int i=1; i<=m; i++)
{
fscanf(in,"%d%d",&a,&b);
add(a,b);
add(b,a);
}
h[0]=Q;
h[1]=1;
dfs(1);
fprintf(out,"%d\n",nrcomp);
for(int i=1; i<=n; i++)
{
int p=lst[i];
while(p)
{
if(c[p]!=0)
{
comp[c[p]].push_back(i);
comp[c[p]].push_back(val[p]);
}
p=nxt[p];
}
}
for(int i=1; i<=nrcomp; i++)
{
std::sort(comp[i].begin(), comp[i].end());
fprintf(out,"%d ",comp[i][0]);
for(int j=1; j<comp[i].size(); j++)
{
if(comp[i][j]!=comp[i][j-1])
fprintf(out,"%d ",comp[i][j]);
}
fprintf(out,"\n");
}
return 0;
}