Pagini recente » Cod sursa (job #3041217) | Cod sursa (job #1359686) | Cod sursa (job #2880755) | Cod sursa (job #834629) | Cod sursa (job #1378892)
#include <cstdio>
#include <vector>
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];
std:: vector<int> lista;
int nrc;
std::vector<int> comp[Q];
int h[Q];
int dfs(int nod, int tata)
{
int up=0;
int p=lst[nod];
h[nod]=h[tata]+1;
lista.push_back(nod);
viz[nod]=1;
int act;
while(p)
{
if(viz[val[p]]==2)
{
p=nxt[p];
continue;
}
if(viz[val[p]]==0)
{
act=dfs(val[p],nod);
if(h[act]<h[up])
up=act;
if(act==nod)
{
nrc++;
while(lista.back()!=nod)
{
comp[nrc].push_back(lista.back());
lista.pop_back();
}
comp[nrc].push_back(lista.back());
up=0;
}
}
else
{
if(h[val[p]]<h[up])
up=val[p];
}
// }
p=nxt[p];
}
viz[nod]=2;
return up;
}
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;
dfs(1,Q-1);
fprintf(out,"%d\n",nrc);
for(int i=1; i<=nrc; i++)
{
for(int j=0; j<comp[i].size(); j++)
fprintf(out,"%d ",comp[i][j]);
fprintf(out,"\n");
}
return 0;
}