URAL 1137Bus Routes (dfs)
2024-09-25 07:05:54
Z - Bus Routes
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
Several bus routes were in the city of Fishburg. None of the routes shared the same section of road, though common stops and intersections were possible. Fishburg old residents stated that it was possible to move from any stop to any other stop (probably making several transfers). The new mayor of the city decided to reform the city transportation system. He offered that there would be only one route going through all the sections where buses moved in the past. The direction of movement along the sections must be the same and no additional sections should be used.
Write a program, which creates one of the possible new routes or finds out that it is impossible.
Input
The first line of the input contains the number of old routes n. Each of the following n lines contains the description of one route: the number of stops m and the list of that stops. Bus stops are identified by positive integers not exceeding 10000. A route is represented as a sequence of m + 1 bus stop identifiers: l1, l2, …, lm, lm+1 = l1 that are sequentially visited by a bus moving along this route. A route may be self-intersected. A route always ends at the same stop where it starts (all the routes are circular).
The number of old routes: 1 ≤ n ≤ 100.
The number of stops: 1 ≤
m ≤ 1000.
The number-identifier of the stop: 1 ≤
l ≤ 10000.
The number of stops: 1 ≤
m ≤ 1000.
The number-identifier of the stop: 1 ≤
l ≤ 10000.
Output
The output contains the number of stops in the new route k and the new route itself in the same format as in the input. The last (
k+1)-th stop must be the same as the first. If it is
impossible to make a new route according to the problem statement then
write 0 (zero) to the output.
k+1)-th stop must be the same as the first. If it is
impossible to make a new route according to the problem statement then
write 0 (zero) to the output.
Sample Input
input | output |
---|---|
3 |
15 2 5 4 2 3 6 5 7 4 1 2 1 4 7 5 2 |
Notes
Here is a picture for the example:
题意就是给你几条旧的路线,让你求能否设计一条新的路线,可以包含这里面的所有路线,dfs变换一下就可以了,但是注意一点就是再回塑的时候不要把标记vis即系清空
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define N 10010
int n,m;
vector<int>ed[N];
bool vis[N][N];
int pa[],t;
void dfs(int u){
int i;
for(i = ;i < (int)ed[u].size() ; i++){
int v = ed[u][i];
if(!vis[u][v]){
vis[u][v] = ;
dfs(v);
}
}
t++;
pa[t] = u;
return ;
}
int main(){
int i,j,u,v;
scanf("%d",&n);
int sum=;
for(i = ; i <= n ; i++){
scanf("%d",&m);
sum+=m;
scanf("%d",&u);
for(j = ; j <= m ; j++)
{
scanf("%d",&v);
ed[u].push_back(v);
u = v;
}
}
dfs();
if(sum!=t-)
printf("0\n");
else{
printf("%d\n",t-);
for(i = t; i > ; i--)
printf("%d ",pa[i]);
printf("%d\n",pa[]);
}
return ;
}
最新文章
- Java NIO3:通道和文件通道
- 企业项目开发--分布式缓存Redis
- 基础篇-struts2的搭建
- openstack 流量控制
- 泛型类型的协变(covariant)和逆变
- 公交部署wifi热点,是否有必要?
- CentOS安装glibc-2.14,错误安装libc.so.6丢失急救办法
- mybatis 自动生成代码(mybatis generator)
- js_6_dom选择
- Linux学习之CentOS(十二)----磁盘管理之 认识ext文件系统(转)
- linux找不到动态链接库 .so文件的解决方法(转自:http://www.cnblogs.com/xudong-bupt/p/3698294.html)
- 【bzoj 4176】 Lucas的数论 莫比乌斯反演(杜教筛)
- ElasticSearch(九):elasticsearch-head插件安装
- c++趣味之变量名,颠覆所有教科书的VisualStudio
- oracle监控
- SortedSet的实现类是TreeSet:它的作用是字为添加到TreeSet中的元素排序。
- 20155219付颖卓《网络对抗》逆向及Bof基础
- Magic Powder - 2 (CF 670_D)
- NetFPGA Demo ——reference_nic_nf1_cml
- CCLabelAtlas的宽度为奇数时的显示bug
热门文章
- SQL Server数据库log shipping 灾备(Part2 )
- Python3+Selenium3+webdriver学习笔记6(多窗口切换处理)
- COGS 2794. 爱摔跤的比利海灵顿
- 在openSUSE 13.1上用gem安装rails无反应: gem install rails
- 2015 ACM/ICPC Asia Regional Changchun Online Pro 1005 Travel (Krsukal变形)
- 得到本地应用程序的EXE的路径
- 洛谷 P2568 GCD
- 【贪心 计数 倍增】bzoj4458: GTY的OJ
- 每天一个linux命令(13):less命令
- 【python】python安装和运行报错汇总