【图论】【DFS】AGC013 B Hamiltonish Path

分析:

很简单的DFS水题。
很容易发现，这个起点和终点的条件是很容易构造的，我们只需要随便从一个点出发，向其中某个方向一直dfs下去，直到走不动了，那个点设为起点。再从另一个方向一直dfs下去，直到走不动了，设为终点。

找起点用栈就可以了。

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<stack> #define SF scanf #define PF printf #define MAXN 100010 using namespace std; struct node{
     int x;node *nxt; }edge[MAXN*2]; node *head[MAXN],*ncnt=edge; void add_edge(int x,int y){
     ++ncnt;ncnt->x=y;ncnt->nxt=head[x];head[x]=ncnt; } int u,v; stack<int> st; vector<int> ans; bool vis[MAXN]; void find_ans(int x,int flag){
     vis[x]=1;if(flag==0)st.push(x);elseans.push_back(x);for(node *v=head[x];v!=NULL;v=v->nxt){
     int u=v->x;if(vis[u]==1)continue; find_ans(u,flag);break;} } int n,m; int main(){
     SF("%d%d",&n,&m);for(int i=1;i<=m;i++){
     SF("%d%d",&u,&v); add_edge(u,v);add_edge(v,u);}find_ans(1,0);while(1){
     int x=st.top();st.pop();if(st.empty())break;ans.push_back(x); }find_ans(1,1);PF("%d\n",int(ans.size()));for(int i=0;i<int(ans.size());i++)PF("%d ",ans[i]); }