Cat Snuke and a Voyage AtCoder - 2660

原题地址
题意:就是让你判断是否能有一条航道（且这个航道只能有一个中转岛，也就是说只能途径一次除了1和n的其他岛），能使第1和第n岛屿连接。
题解：两种办法

• 第一种直接暴力，直接判断1和n之间有且仅有一个中转岛
• 第二种深搜
  第一种代码：

#include<iostream>
#include<cstdio>
using namespace std;
int i,j,n,m,x[200003]= {0},a,b,num=0,num1=0;
int main()
{
    cin>>n>>m;
    for(i=0; i<m; i++)
    {
        scanf("%d %d",&a,&b);
        if(a==1)
            x[b]++;
        if(b==n)
            x[a]++;
    }
    int flag=0;
    for(i=0; i<n; i++)
    {
        if(x[i]==2)
        {
            flag=1;
            break;
        }
    }
    if(flag==1)
        cout<<"POSSIBLE"<<endl;
    else
        cout<<"IMPOSSIBLE"<<endl;
}

第二种代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <iomanip>
#include <string.h>
#include <algorithm>
//#include <bits/stdc++.h>
#include    <vector>
#define INF 999999999
# include <cstdio>
# include <cstdlib>
using namespace std;
#define ll long long
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
int n ,k ,num=0, fa =0;
struct shi{
    int x ;
    int y ;
    int next;
}S[200010];
int head[200010];
int dfs(int yy,  int a){
    if(yy==n&&a==2)
    {
        return 1;
    }
    for(int i = head[yy];i!=-1;i=S[i].next)
    {
        int k = S[i].y;
        if(dfs(k,a+1))
            return 1;
    }
    return 0;
}
int main(){
   cin >>n>>k;
   memset(head,-1,sizeof(head));
   for(int i=1;i<=k;i++)
   {
       int t , l;
       cin>>t >>l;
       S[num].x = t , S[num].y = l;
       S[num].next = head[t];
       head[t] = num++;
   }
   if(dfs(1 , 0 ))
    cout<<"POSSIBLE"<<endl;
   else cout<<"IMPOSSIBLE"<<endl;
    return 0;
}