首页 > 代码库 > URAL 1077 Travelling Tours(统计无向图中环的数目)

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

inputoutput
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 = 205;
const int M = 24005;
int  n,m,k,l,tot=0;
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,0);met(pre,0);
    queue<int>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<vec[u].size();i++){
            int v=vec[u][i];
            if(!vis[v]){
                pre[v]=u;vis[v]=1;
                q.push(v);
            }
        }
    }
}
int main() {
    int u,v;
    for(int i=0;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=1;i<=tot;i++){
        printf("%d",ans[i].size());
        for(int j=0;j<ans[i].size();j++){
            printf(" %d",ans[i][j]);
        }printf("\n");
    }
    return 0;
}

 

URAL 1077 Travelling Tours(统计无向图中环的数目)