1077. Travelling Tours

Time limit: 1.0 second Memory limit: 64 MB

There are

 

N

 cities numbered from 1 to

 

N

 (1 ≤ 

N ≤ 200) and

 

M

 two-way roads connect them. There are at most one road between two cities. In summer holiday, members of DSAP Group want to make some traveling tours. Each tour is a route passes

 

K

 different cities (

K > 2)

 

T

₁,

 

T

₂, …,

 

T_K

 and return to

 

T

₁. Your task is to help them make

 

Ttours such that:

1. Each of these T tours has at least a road that does not belong to (T−1) other tours.
2. T is maximum.

Input

The first line of input contains

 

N

 and

 

M

 separated with white spaces. Then follow by

 

M

 lines, each has two number

 

H

 and

 

T

 which means there is a road connect city

 

Hand city

 

T.

Output

You must output an integer number

 

T — the maximum number of tours. If

 

T > 0, then

 

T

 lines followed, each describe a tour. The first number of each line is

 

K — the amount of different cities in the tour, then

 

K

 numbers which represent

 

K

 cities in the tour.

If there are more than one solution, you can output any of them.

Sample

input	output
5 71 21 31 42 42 33 45 4	33 1 2 43 1 4 34 1 2 3 4

Problem Author: Nguyen Xuan My (Converted by Dinh Quang Hiep and Tran Nam Trung)

 

Problem Source: From the third contest at Department of Mathematics and Informatics - Natural Sciences College - National University of HaNoi.

***************************************************************************************

并查集；

每次求出一个环后，标记结点，直到找出所有的环

***************************************************************************************

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #include
             
               7 #include
              
                8 using namespace std; 9 int head[1001],fa[1001];10 int n,m,i,j,k,cnt;11 int link[1001][1001];//联系数组12 int vis[1001];//标记结点所用13 vector
               
                ans[180000];//存储结果14 void make()15 {16 for(int it=0;it<=n;it++)17 {18 fa[it]=it;19 link[it][0]=0;20 ans[it].clear();21 }22 }23 int find(int x)//并查集24 {25 if(fa[x]!=x)26 fa[x]=find(fa[x]);27 return fa[x];28 }29 void work(int x,int y)30 {31 memset(vis,0,sizeof(vis));32 memset(head,-1,sizeof(head));//前驱存储33 head[x]=-1;34 vis[x]=1;35 queue
                
                 Q;36 Q.push(x);37 while(!Q.empty())38 {39 int h=Q.front();40 Q.pop();41 if(h==y)42 {43 ans[cnt].push_back(y);44 for(int it=head[y];it!=-1;it=head[it])45 ans[cnt].push_back(it);46 cnt++;47 return;48 }49 for(int it=1;it<=link[h][0];it++)50 {51 int gs=link[h][it];//把没访问的节点放入队列52 if(!vis[gs])53 {54 Q.push(gs);55 vis[gs]=1;56 head[gs]=h;57 }58 }59 60 }61 62 63 }64 int main()65 {66 cin>>n>>m;67 int x,y;68 cnt=0;69 make();70 for(i=1;i<=m;i++)71 {72 cin>>x>>y;73 int fs=find(x);74 int ds=find(y);75 if(fs==ds)76 {77 work(x,y);78 }79 else80 {81 link[x][++link[x][0]]=y;82 link[y][++link[y][0]]=x;83 fa[fs]=ds;84 }85 86 }87 cout<
                 
                  <