URAL 1077 Travelling Tours（统计无向图中环的数目）-白红宇

URAL 1077 Travelling Tours（统计无向图中环的数目）

阅读量：6253 次

发布时间：2019-06-22

本文共 2123 字，大约阅读时间需要 7 分钟。

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_K and return to

₁. Your task is to help them make

T tours such that:

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

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

H and city

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)

【分析】给你一张无向图，问你图中最多存在多少个环。用并查集来做，每次输入一条边，如果两个顶点不在同一集合中，就把他俩合为一个集合中，如果已经在一个集合中了，

说明只要加上这条边，就会形成一个环，然后就BFS找就行了，用pre数组记录路径。

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                #include 
                
                 #define inf 0x3f3f3f3f#define met(a,b) memset(a,b,sizeof a)#define pb push_backtypedef long long ll;using namespace std;const int N = 205;const int M = 24005;int n,m,k,l,tot=0;int parent[N],pre[N],vis[N];vector
                 
                  vec[N],ans[N*N];int Find(int x){ if(parent[x]!=x)parent[x]=Find(parent[x]); return parent[x];}void Union(int x,int y){ x=Find(x);y=Find(y); if(x==y)return; else parent[y]=x;}void bfs(int s,int t){ met(vis,0);met(pre,0); queue
                  
                   q; q.push(s);vis[s]=1; while(!q.empty()){ int u=q.front();q.pop(); if(u==t)return; for(int i=0;i

转载于:https://www.cnblogs.com/jianrenfang/p/5997525.html

你可能感兴趣的文章