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

时间：2023-03-09 03:50:50
URAL 1077 Travelling Tours（统计无向图中环的数目）

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) T1, T2, …, TK
and return to T1. Your task is to help them make T tours 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 H and 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 7

1 2

1 3

1 4

2 4

2 3

3 4

5 4

3

3 1 2 4

3 1 4 3

4 1 2 3 4
Problem Author: Nguyen Xuan My (Converted by Dinh Quang Hiep and Tran Nam Trung)
【分析】给你一张无向图，问你图中最多存在多少个环。用并查集来做，每次输入一条边，如果两个顶点不在同一集合中，就把他俩合为一个集合中，如果已经在一个集合中了，说明只要加上这条边，就会形成一个环，然后就BFS找就行了，用pre数组记录路径。
#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <string>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#define inf 0x3f3f3f3f

#define met(a,b) memset(a,b,sizeof a)

#define pb push_back

typedef long long ll;

using namespace std;

const int N = ;

const int M = ;

int  n,m,k,l,tot=;

int parent[N],pre[N],vis[N];

vector<int>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,);met(pre,);

    queue<int>q;

    q.push(s);vis[s]=;

    while(!q.empty()){

        int u=q.front();q.pop();

        if(u==t)return;

        for(int i=;i<vec[u].size();i++){

            int v=vec[u][i];

            if(!vis[v]){

                pre[v]=u;vis[v]=;

                q.push(v);

            }

        }

    }

}

int main() {

    int u,v;

    for(int i=;i<N;i++)parent[i]=i;

    scanf("%d%d",&n,&m);

    while(m--){

        scanf("%d%d",&u,&v);

        int x=Find(u);int y=Find(v);

        if(x==y){

            bfs(u,v);

            ans[++tot].push_back(v);

            while(pre[v]){

                ans[tot].pb(pre[v]);

                v=pre[v];

            }

        }else{

            vec[u].pb(v);vec[v].pb(u);

            Union(u,v);

        }

    }

    printf("%d\n",tot);

    for(int i=;i<=tot;i++){

        printf("%d",ans[i].size());

        for(int j=;j<ans[i].size();j++){

            printf(" %d",ans[i][j]);

        }printf("\n");

    }

    return ;

}