来自"NOCOW"

一个有n个点，m条边，连同分量为p的图，一定有m-n+p个环，剩下的就可以用搜索解决了

program cao;
const
  maxn=200;
 
var
  map,back:array[0..maxn,0..maxn] of boolean;
  level,ans:array[0..maxn] of longint;
  flag:array[0..maxn] of boolean;
  a,b,c,d,e,f,g,h,i,j,k,l,n,m,p,q,x,y:longint;
 
procedure init;
begin
  read(n,m);
  for i:=1 to m do
  begin
    read(a,b);
    map[a,b]:=true;
    map[b,a]:=true;
  end;
end;
 
procedure dfs(v:longint);
var
  i:longint;
begin
  for i:=1 to n do
    if (map[v,i])and(level[i]=0) then
    begin
      level[i]:=level[v]+1;
      map[v,i]:=false;
      map[i,v]:=false;
      back[v,i]:=true;
      back[i,v]:=true;
      dfs(i);
    end;
end;
 
function search(depth,now,target:longint):boolean;
var
  i:longint;
begin
  flag[now]:=true;
  ans[depth]:=now;
  if now=target then
  begin
    p:=depth;
    exit(true);
  end;
  for i:=1 to n do
    if (back[i,now])and(flag[i]=false) then
      if search(depth+1,i,target) then exit(true);
  exit(false);
end;
 
procedure main;
begin
  p:=0;
  for i:=1 to n do
    if level[i]=0 then
    begin
      level[i]:=1;
      inc(p);
      dfs(i);
    end;
  writeln(m-n+p);
 
  for i:=1 to n do
    for j:=i+1 to n do
    if map[i,j] then
    begin
      fillchar(flag,sizeof(flag),0);
      p:=0;
      search(1,i,j);
      write(p);
      for k:=1 to p do
        write(‘ ‘,ans[k]);
      writeln;
    end;
end;
 
begin
  init;
  main;
end.

http://www.withflying.com/?p=139

//感谢神牛，现在贴个CPP的
#include <cstdio>
#include <cstring>
 
const int oo=301*201,maxn=202;
 
int n,m,x,y,e[oo],next[oo],lis[maxn],tot,stack[maxn],l,level[maxn],p;
bool mk[maxn];
 
inline void Add(int x,int y)
{	e[++l]=y;next[l]=lis[x];lis[x]=l;	}
 
void Dfs(int u){
	mk[u]=1;
	int v;
	for (int i=lis[u];i;i=next[i]){
		v=e[i];
		if (!mk[v])	Dfs(v);
	}
}
 
void dfs(int u){
	stack[++tot]=u;level[u]=tot;mk[u]=1;
	int v;
	for (int i=lis[u];i;i=next[i]){
		v=e[i];
		if (!mk[v])	dfs(v);
		else{
			if (level[u]-level[v]>1){
				printf("%d",level[u]-level[v]+1);
				for (int j=level[v];j<=level[u];j++)
					printf(" %d",stack[j]);
				printf("\n");
			}
		}
	}
	tot--;
}
 
int main(){
	freopen("s.in","r",stdin);
	freopen("s.out","w",stdout);
 
	scanf("%d%d",&n,&m);
 
	for (int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		Add(x,y),Add(y,x);
	}
 
 
	for (int i=1;i<=n;i++)
	if (!mk[i])
		p++,Dfs(i);
 
	printf("%d\n",m-n+p);
	memset(mk,0,sizeof(mk));
 
	for (int i=1;i<=n;i++)
	if (!mk[i])
		dfs(i);
 
	return 0;
}

http://www.withflying.com

---

赞同楼上的做法 但是搜索我想可以用最小生成树的克鲁斯卡尔算法来优化 每次加入一条边 如果连接两个不同的连通块 则连通后顺便把边加进去 如果出现了环 那么就以头到尾进行宽搜 因为维护的连通块始终是棵树 所以只要顺推就能找到并输出 此方法证明成功。

program cyd;
  var
    f:array[1..200]of integer;
    b:array[1..200,0..200]of integer;
    d,pre:array[1..200]of integer;
    p:array[1..200]of boolean;
    e:array[1..40000,1..2]of integer;
    i,j,k,l,m,n,a,c,head,tail,now,x,y:longint;
  function find(v:integer):integer;
    begin
      if f[v]=v then exit(v)
                else f[v]:=find(f[v]);
      exit(f[v]);
    end;
  begin
    readln(n,m);
    for i:=1 to m do
      begin
        read(x,y);
        e[i,1]:=x; e[i,2]:=y;
      end;
    for i:=1 to n do f[i]:=i;
    j:=n;
    for i:=1 to m do
      begin
        x:=find(e[i,1]);
        y:=find(e[i,2]);
        if x<>y then
          begin
            f[x]:=y;
            dec(j);
          end;
      end;
    writeln(m-n+j);
    for i:=1 to n do f[i]:=i;
    for i:=1 to m do
      begin
        x:=find(e[i,1]);
        y:=find(e[i,2]);
        if x<>y then
          begin
            f[x]:=y;
            x:=e[i,1]; y:=e[i,2];
            inc(b[x,0]);
            b[x,b[x,0]]:=y;
            inc(b[y,0]);
            b[y,b[y,0]]:=x;
          end
                else
          begin
            fillchar(p,sizeof(p),0);
            fillchar(pre,sizeof(pre),0);
            x:=e[i,1]; y:=e[i,2];
            head:=1; tail:=1; d[1]:=x; p[x]:=true;
            while head<=tail do
              begin
                now:=d[head];
                for j:=1 to b[now,0] do
                  if not p[b[now,j]] then
                    begin
                      p[b[now,j]]:=true;
                      inc(tail);
                      d[tail]:=b[now,j];
                      pre[b[now,j]]:=now;
                      if d[tail]=y then break;
                    end;
                if d[tail]=y then break;
                inc(head);
              end;
          j:=y;
          k:=0;
          while j<>0 do
            begin
              inc(k);
              d[k]:=j;
              j:=pre[j];
            end;
          write(k);
          for j:=1 to k do
            write(' ',d[j]);
          writeln;
        end;
    end;
  end.