题目链接
需要注意的点
- -0000与0000在int下是等效的故而无法据此判断id为该两个数的男孩、女孩之性别，所以需要输入字符串来判断人物性别。
- 没了。
DFS（TE）
- 递归初始深度为0，当深度为3时判断当前节点是否为心动男、女孩。
- 根据AB的性别相同与否分为两个模式，当AB为相同性别时4个人的性别都是相同的，否则A的朋友C、B的朋友D应为异性，据此根据递归深度的不同对下一层节点的性别稍作判断。
然而DFS复杂度过高，当AB朋友很多时会超时。
// #include <bits/stdc++.h>
// can mix cin/cout with scanf/printf with debug mode
// can only use cin/cout or scanf/printf without debug mode
// notice:
// 1) static map or tree can use Node
// 2) dynamic map or tree can only use Node*
// 3) int bk[maxn] is much faster than unordered_set; bk << unordered_set << set
// 4) int bk[maxn] = {0} is much faster than memset(bk, 0, sizeof(bk));
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <deque>
#include <iostream>
#include <iomanip>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <climits>#define uu(i, a, b) for (int i = (a), _upper_bound = (b); i < _upper_bound; ++i)
#define dd(i, a, b) for (int i = (a), _lower_bound = (b); i > _lower_bound; --i)
#define each(it, a) for(auto & (it) : (a))
#define pf printf
#define sf scanf
#define _max(a, b) ((a) > (b) ? (a) : (b))
#define _min(a, b) ((a) < (b) ? (a) : (b))typedef long long ll;
const double eps = 1e-8;
#define lowbit(x) (x&(-x))
#define equ(a, b) (fabs(a - b) < eps)
#define lcm(a, b) (a / gcd(a, b) * b)
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}using namespace std;
const int maxn = 1e5+1;int N, M, K;struct Node{
int isg; // is girl vector<int> n;
}node[maxn];void print(std::vector<int> &v){
uu(i, 1, v.size()-1){
if(i == 1) std::cout << setw(4) << setfill('0') << v[i];else std::cout << " " << setw(4) << setfill('0')<< v[i];}std::cout << std::endl;
}#define pii pair<int, int>
#define piv pair<int, vector<int>>vector<vector<int>> re;
vector<int> tmp;
int mode, tofind;void dfs(int x, int dep, int bk[], int s, int e){
bk[x] = 1;tmp.push_back(x);if(dep == 3 and x == e){
re.push_back(tmp);bk[x] = 0;tmp.pop_back();return ;}// each(to, node[x].n){
// if(bk[to] == 0) dfs(to, dep+1, bk, s, e);// }if(mode == 1){
// find same gender alwayseach(to, node[x].n){
if(bk[to] == 0 and node[to].isg == tofind){
dfs(to, dep+1, bk, s, e);}} }else{
each(to, node[x].n){
if(bk[to] == 0){
if(dep == 0 and node[to].isg == tofind) dfs(to, dep+1, bk, s, e);if(dep == 1 and node[to].isg != tofind) dfs(to, dep+1, bk, s, e);if(dep == 2 and to == e) dfs(to, dep+1, bk, s, e);}} }bk[x] = 0;tmp.pop_back();return ;
}bool cmp(vector<int> & v1, vector<int> & v2){
if(v1[1] != v2[1]) return v1[1] < v2[1];else return v1[2] < v2[2];
}int main(){
#ifndef DEBUGios::sync_with_stdio(false);std::cin.tie(nullptr);#endif#ifdef LOCALfreopen("in", "r", stdin);freopen("o", "w", stdout);#endif// cout << setiosflags(ios::fixed);// cout << setprecision(2);// cout << setw(2) << setfill('0'); // add this every time when cout int with width and left padding '0'cin >> N >> M;uu(i, 0, M){
string s1 , s2;cin >>s1 >> s2;int x, y;sscanf(s1.c_str(), "%d", &x);sscanf(s2.c_str(), "%d", &y);if(x < 0) x = -x;if(y < 0) y = -y;if(s1[0] == '-') node[x].isg = 1;else node[x].isg = 0;if(s2[0] == '-') node[y].isg = 1;else node[y].isg = 0;node[x].n.push_back(y);node[y].n.push_back(x);}cin >> K;while(K--){
int x , y;cin >> x >> y;re.clear();tmp.clear();int bk[maxn] = {
0}; if(x < 0) x = -x;if(y < 0) y = -y;if(node[x].n.size() == 0 or node[y].n.size() == 0){
cout << 0 << endl;continue;}if(node[x].isg == node[y].isg) mode = 1;else mode = 0;tofind = node[x].isg;dfs(x, 0, bk, x, y);cout << re.size() << endl;sort(re.begin(), re.end(), cmp);each(v, re){
print(v);}}return 0;
}
简化DFS
思考各自从AB出发得到朋友CD，此时仅需要根据AB性别相同与否分别判断CD性别即可，符合条件的CD加入答案最后对答案排序即可。
需要注意：
- 添加Ａ、Ｂ朋友到Ｃ、Ｄ集合中去仅需要添加Ａ、Ｂ的同性朋友即可。
- 根据条件１，当Ａ、Ｂ同性时ＡＢ可能会互相添加入各自的朋友集合ＣＤ，因此需要避免把B直接为A朋友的情况添加入答案，根据以上算法，A添加B进入A朋友集合C，B也会把A添加入B朋友集合D，此时CD中各自有A和Ｂ（他们已经是朋友了，会加入到答案中去）。
// #include <bits/stdc++.h>
// can mix cin/cout with scanf/printf with debug mode
// can only use cin/cout or scanf/printf without debug mode
// notice:
// 1) static map or tree can use Node
// 2) dynamic map or tree can only use Node*
// 3) int bk[maxn] is much faster than unordered_set; bk << unordered_set << set
// 4) int bk[maxn] = {0} is much faster than memset(bk, 0, sizeof(bk));
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <deque>
#include <iostream>
#include <iomanip>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <climits>#define uu(i, a, b) for (int i = (a), _upper_bound = (b); i < _upper_bound; ++i)
#define dd(i, a, b) for (int i = (a), _lower_bound = (b); i > _lower_bound; --i)
#define each(it, a) for(auto & (it) : (a))
#define pf printf
#define sf scanf
#define _max(a, b) ((a) > (b) ? (a) : (b))
#define _min(a, b) ((a) < (b) ? (a) : (b))typedef long long ll;
const double eps = 1e-8;
#define lowbit(x) (x&(-x))
#define equ(a, b) (fabs(a - b) < eps)
#define lcm(a, b) (a / gcd(a, b) * b)
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}using namespace std;
const int maxn = 1e5+1;int N, M, K;struct Node{
int isg; // is girl set<int> n;
}node[maxn];#define pii pair<int, int>
#define piv pair<int, vector<int>>void print(pii &p){
cout << setw(4) << setfill('0') << p.first << " " << setw(4) << setfill('0') << p.second << endl;
}vector<pii> re;bool cmp(pii & v1, pii & v2){
if(v1.first != v2.first) return v1.first < v2.first;else return v1.second < v2.second;
}int main(){
#ifndef DEBUGios::sync_with_stdio(false);std::cin.tie(nullptr);#endif#ifdef LOCALfreopen("in", "r", stdin);freopen("o", "w", stdout);#endif// cout << setiosflags(ios::fixed);// cout << setprecision(2);// cout << setw(4) << setfill('0'); // add this every time when cout int with width and left padding '0'cin >> N >> M;uu(i, 0, M){
string s1 , s2;cin >>s1 >> s2;int x, y;sscanf(s1.c_str(), "%d", &x);sscanf(s2.c_str(), "%d", &y);if(x < 0) x = -x;if(y < 0) y = -y;if(s1[0] == '-') node[x].isg = 1;else node[x].isg = 0;if(s2[0] == '-') node[y].isg = 1;else node[y].isg = 0;node[x].n.insert(y);node[y].n.insert(x);}cin >> K;while(K--){
int x , y;cin >> x >> y;re.clear();if(x < 0) x = -x;if(y < 0) y = -y;if(node[x].n.size() == 0 or node[y].n.size() == 0){
cout << 0 << endl;continue;}vector<int> af, bf;each(fri, node[x].n){
if(node[fri].isg == node[x].isg and fri != y) af.push_back(fri);}each(fri, node[y].n){
if(node[fri].isg == node[y].isg and fri != x) bf.push_back(fri);}each(a, af){
each(b, bf){
if(node[x].isg == node[y].isg){
if(node[a].isg == node[b].isg and node[a].n.find(b) != node[a].n.end()){
re.push_back({
a, b});}}else{
if(node[a].isg != node[b].isg and node[a].n.find(b) != node[a].n.end()){
re.push_back({
a, b});} }}}cout << re.size() << endl;sort(re.begin(), re.end(), cmp);each(p, re){
print(p);}}return 0;
}