C - Least Crucial Node

题目链接：https://cn.vjudge.net/contest/247936#problem/C

具体大意：给你起点和中点，总点数，边数。求到终点的最小割点。

具体思路：可以用tarjan算法来求割点，不过还有一种比较朴素的求法。假设一共有五个点，起点是1，终点是5.我们可以先将除起点和终点之外的点罗列出来，然后假设某一个点以及这个点所连的边不存在，然后再看一下其他点中到终点的个数，这样也可以求出最小割点来。（过会再更新tarjan算法求割点）

AC代码：

 #include<iostream>

 #include<string>

 #include<cstring>

 #include<iomanip>

 #include<cmath>

 #include<algorithm>

 #include<stdio.h>

 #include<map>

 #include<queue>

 #include<stack>

 #include<vector>

 using namespace std;

 # define maxn

 # define  ll long long

 #define inf 0x3f3f3f3f

 #define ll_inf 0x3f3f3f3f3f3f3f3f

 vector<int >q[maxn];

 int n,m,fin;

 int vis[maxn];

 bool flag;

 void   dfs(int t1,int t2)

 {

     if(t1==fin)

     {

         flag=true;

         return ;

     }

     int len=q[t1].size();

     for(int i=; i<len; i++)

     {

         int temp=q[t1][i];

         if(q[t1][i]==t2)continue;

         if(vis[temp]==)

         {

             vis[temp]=;

             dfs(temp,t2);

         }

     }

 }

 int Find(int t)

 {

     int ans=;

     for(int i=; i<=n; i++)//cal except i

     {

         flag=false;

         memset(vis,,sizeof(vis));

         if(i==t||i==fin)continue;

         dfs(i,t);

         if(flag)ans++;

     }

     return ans;

 }

 void init(){

 for(int i=;i<=n;i++){

     q[i].clear();

 }

 }

 int main()

 {

     while(cin>>n&&n)

     {

         init();

         cin>>fin>>m;

         for(int i=; i<=m; i++)

         {

             int u,v;

             cin>>u>>v;

             q[u].push_back(v);

             q[v].push_back(u);

         }

         int minn=inf, t;

         for(int i=; i<=n; i++)//erase i

         {

             if(i==fin)continue;

             if(Find(i)<minn||(Find(i)==minn&&i<t))

             {

                 minn=Find(i);

                 t=i;

             }

         }

         cout<<t<<endl;

     }

     return ;

 }