首页 > 代码库 > URAL 1077 Travelling Tours(统计无向图中环的数目)
URAL 1077 Travelling Tours(统计无向图中环的数目)
Travelling Tours
Time limit: 1.0 second
Memory limit: 64 MB
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:
- 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 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 = 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(统计无向图中环的数目)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。