天天看點

Atcoder ABC266 F 題解ABC266F 題解

ABC266F 題解

今天口胡 ABC266,看到這道題,秒切了,早知道打了那一場。

題面

給一個 n n n 個點 n n n 條邊的簡單無向連通圖,給定 q q q 個詢問求:

  • 給定 u i u_i ui​ 和 v i v_i vi​,它們是否隻有一個簡單路徑。

題解

n n n 條邊的簡單無向連通圖,顯然為一個基環樹,概念請左轉部落格。

這道題顯然找環,将環上所有的邊删掉,看兩個點是否連通。(不連通就得走環,走環肯定有兩種情況)。

并查集 + 深搜。

Code

#include <bits/stdc++.h>

#define int long long
// FOR templates.
#define rep(i, s, n, k) for(int i = s;i <= n;i += k)
#define repn(i, s, n, k) for(int i = s;i < n;i += k)
#define pre(i, s, n, k) for(int i = s;i >= n;i -= k)
#define pren(i, s, n, k) for(int i = s;i > n;i -= k)
// Abbr for STL.
#define pii pair<int, int>
#define pdd pair<double, double>
#define mpi map<int, int>
#define pii pair<int, int>
#define pdd pair<double, double>
#define vc vector<int>
#define mpp map<int, int>
#define arr(k, n) int k[n]
#define all(v) v.begin(), v.end()
// CIN templates, proven very useful.
#define cn(n) int n;cin >> n
#define cm(n) cin >> n
// Abbr for funcs.
#define pb push_back
#define mset memset
// #define files
using namespace std;
const int MAXN = 0x3f3f3f3fLL;
const int MOD1 = 1000000007LL;
const int MOD2 = 998244353LL;
int d[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int gcd(int a, int b) {if(b == 0) return a;return gcd(b, a % b);}
inline int lowbit(int x) {return x & (-x);}
inline int lcm(int a, int b) {return a * b / gcd(a, b);}

vc gv[200001]; int fa[200001], fat[200001];
void add_edge(int u, int v){
	gv[u].pb(v); gv[v].pb(u);
}
void dfs(int n, int f){
	fa[n] = f;
	repn(i, 0, gv[n].size(), 1){
		if(gv[n][i] == f) continue;
		dfs(gv[n][i], n);
	}
}
int FindFather(int n){
	if(fat[n] == n) return n;
	return fat[n] = FindFather(fat[n]);
}
bool Union(int u, int v){
	if(FindFather(u) == FindFather(v)) return true;
	fat[FindFather(u)] = FindFather(v);
	return false;
}
pii make_pair(int a, int b){
	if(a > b) swap(a, b);
	return (pii){a, b};
}

signed main(){
#ifdef files
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cn(n); rep(i, 1, n, 1){
    	fat[i] = i;
	}
	map<pii, int> mp; bool fnd = 0;
	repn(i, 0, n, 1){
    	cn(u); cn(v);
    	mp[make_pair(u, v)] = 1;
    	if(!fnd && Union(u, v)){
    		dfs(u, -1); int p = v;
    		while(p != u){
    			mp[make_pair(p, fa[p])] = 0; p = fa[p];
			}
			mp[make_pair(u, v)] = 0; fnd = 1;
		}
		add_edge(u, v);
	}
	rep(i, 1, n, 1) fat[i] = i;
	map<pii, int>::iterator it;
	for(it = mp.begin();it != mp.end();it++){
		if(it->second > 0) Union(it->first.first, it->first.second);
	}
	cn(q); while(q--){
		cn(x); cn(y);
		if(FindFather(x) != FindFather(y)){
			cout << "No" << endl;
		}
		else{
			cout << "Yes" << endl;
		}
	}
    return 0;
}

/*
 *  things to check
 *  1.  int overflow or long long memory need
 *  2.  recursion/array/binary search/dp/loop bounds
 *  3.  precision
 *  4.  special cases(n=1,bounds)
 *  5.  delete debug statements
 *  6.  initialize(especially multi-tests)
 *  7.  = or == , n or m ,++ or -- , i or j , > or >= , < or <=
 *  8.  keep it simple and stupid
 *  9.  do not delete, use // instead
 *  10. operator priority
 *  11. is there anything extra to output?
 *  12. THINK TWICE CODE ONCE, THINK ONCE DEBUG FOREVER
 *  13. submit ONCE, AC once. submit twice, WA forever
 *  14. calm down and you'll get good rank
 *  15. even a bit wrong scores zero
 *  16. ...
 **/
           

繼續閱讀