codeforces 1276B dfs+技巧

题意：给了一个无向图和a，b两点。问存在多少对x，y，使得x到y的路上必须经过a，b。x,y和y,x算作一种情况。

思路：很明显就能想到。如果存在环，环中的点包括了a或者b，则答案为0，否则答案为a和b两边的点的数量积。

　　最初的想法太复杂，看到了一个特别简单的写法能之间秒。

　　可以先对a点进行标记，然对b点进行dfs，对每一个遍历到的点进行cnt++。

　　统计cnt为1的点的个数记作sumb。

　　cnt的值不变，然后同样的再对b进行同样的操作。

　　最后统计cnt为1的点为a能单独到的点的个数suma，cnt为2的点为共有的点的个数toge。

　　最后b能单独到的点的个数为sumb-toge

　　a能单独到的点的个数为suma-sumb+toge；

　　求积即可

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <vector> 
// #include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define sp ' '
#define endl '
'
#define inf  0x3f3f3f3f;
#define FOR(i,a,b) for( int i = a;i <= b;++i)
#define bug cout<<"--------------"<<endl
#define P pair<int, int>
#define fi first
#define se second
#define pb(x) push_back(x)
#define ppb() pop_back()
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define sca3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c))
#define sca2(a,b) scanf("%d %d",&(a),&(b))
#define sca(a) scanf("%d",&(a));
#define sca3ll(a,b,c) scanf("%lld %lld %lld",&(a),&(b),&(c))
#define sca2ll(a,b) scanf("%lld %lld",&(a),&(b))
#define scall(a) scanf("%lld",&(a));


using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a, ll b, ll mod){ll sum = 1;while (b) {if (b & 1) {sum = (sum * a) % mod;b--;}b /= 2;a = a * a % mod;}return sum;}

const double Pi = acos(-1.0);
const double epsilon = Pi/180.0;
const int maxn = 2e5+10;
int n,m,a,b;        
int vis[maxn];
int cnt[maxn];
vector<int>v[maxn];
void dfs(int x)
{    
    for(int i = 0;i < v[x].size(); ++i){
        int y = v[x][i];
        if(vis[y]) continue;
        vis[y] = 1;
        cnt[y]++;
        dfs(y);
    }
}
void clearr()
{
    rep(i,1,n){
        vis[i] = 0;
        cnt[i] = 0;
        v[i].clear();
    }
    //v.clear();
}
int main()
{
//    freopen("input.txt", "r", stdin);
    int _;
    scanf("%d",&_);
    while(_--)
    {
        cin>>n>>m>>a>>b;

        clearr();
        rep(i,1,m){
            int x,y;
            cin>>x>>y;
            v[x].pb(y);
            v[y].pb(x);
        }
        vis[a] = 1;vis[b]=1;
        dfs(b);
/*        rep(i,1,n){
            cout<<cnt[i]<<sp;
        }
        cout<<endl;*/
        ll sumb = 0;
        rep(i,1,n){
            if(cnt[i] == 1){
                sumb++;
            }
            vis[i] = 0;
        }
        vis[a] = 1;vis[b]=1;
        dfs(a);
/*        rep(i,1,n){
            cout<<cnt[i]<<sp;
        }
        cout<<endl;*/
        ll suma = 0,toge = 0;
        rep(i,1,n){
            if(cnt[i]==1){
                suma++;
            }
            else if(cnt[i] == 2){
                toge++;
            }
        }
    //    cout<<sumb<<sp<<suma<<sp<<toge<<endl;
        sumb -= toge;
        suma -= sumb;
        ll ans = suma * sumb;
        cout<<ans<<endl;

    }
}