题意:给出一个简单图,图是连通的。求一条至少包含两个点的路径,满足:1、路径上的点只走过一次; 2、与此路径两个端点直接相连的点必须要在路径里。
tags:要满足条件,一定是从度最小的点开始搜。然后只要dfs搜下去,直到发现两端点能到达的点都走过时,记录下路径即可。
// B #include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i>=a;i--) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f typedef long long ll; const int N = 200005; int n, m, d[N], ans, path[N], mx=INF, mi; bool vis[N], flag=0; vector<int > G[N]; void dfs(int u, int fa) { vis[u]=1; bool flag1=0; for(auto v : G[u]) if(vis[v]==0) { flag1=1; dfs(v, u); if(flag==1) break; } if(flag1==0) { bool flag2=0; for(auto v : G[mi]) if(vis[v]==0) flag2=1; if(flag2==0) flag=1; } if(flag==1) path[++ans]=u; } int main() { scanf("%d %d", &n, &m); int u, v; rep(i,1,m) { scanf("%d %d", &u, &v); G[u].push_back(v); G[v].push_back(u); d[u]++, d[v]++; } rep(i,1,n) mx=min(mx, d[i]); rep(i,1,n) if(mx==d[i]) { mi=i; dfs(i, i); if(flag==1) break; } printf("%d ", ans); per(i,ans,1) printf("%d ", path[i]); return 0; }
题意:周长为 L的圆,有 n只蚂蚁分别在x[i]点开始向顺时针或逆时针方向以1m/s行走。两只蚂蚁如果相撞,各自返回向相反方向走。问在T时间 n只蚂蚁所在的位置。