题目大意
题目描述
Alice 和 Bob 在一个无向简单图上玩改进版的井字棋游戏。这个图有 n 个顶点（代表方格）和 m 条边。
游戏规则如下：
-
初始时，所有顶点都是空的。
-
两人轮流行动，Alice 先手。
-
在 Alice 的回合，她选择一个空的顶点并画上 X。
-
在 Bob 的回合，他选择一个空的顶点并画上 O。
-
游戏总共进行 5 个回合，也就是说 Alice 总是行动 3 次，Bob 总是行动 2 次。
-
如果 Alice 能够将她画了 X 的 3 个顶点连成一条长度为 3 的路径（注意：这 3 个顶点在路径中的顺序不一定与她落子的顺序相同），那么 Alice 获胜。如果 Bob 能阻止这一切发生，则 Bob 获胜。
假设双方在第一步之后都采取完美策略。请计算：Alice 有多少种可能的第一步选择，使得无论 Bob 随后如何应对，她都必胜？
输入格式
第一行包含两个由空格分隔的整数 n 和 m（5≤n≤2×105,0≤m≤min(2×105,n(n−1)/2)），分别表示图的顶点数和边数。
接下来 m 行，每行包含两个由空格分隔的整数 u 和 v（1≤u,v≤n），表示顶点 u 和 v 之间有一条边。
保证图中没有自环和重边。
输出格式
输出一个整数，表示能让 Alice 必胜的初始落子位置的数量。
样例输入
1
2
3
4
5
6
7
8
9
10
| 8 9
1 2
1 4
1 5
2 3
2 7
3 4
3 5
3 6
4 6
|
样例输出
样例解释
对于该图，如果 Alice 第一步下在顶点 1、2、3、4 或 5，那么在双方完美发挥的情况下，她必定能获胜。
以第一步下在顶点 1 为例，其中一种可能的游戏进程是：
思路讲解
遇到图上问题，没有特殊结构以及这个数据比较大，那么基本上就可以排除 dp 的可能性了。
那说白了，我们还有其他工具吗？
我们回归原始，对度数进行分类讨论。
首先，度数 ≥ 4，一定是必胜起始点。
度数为 3 的时候，不难得出：⚠️ 注意：需要两个，否则你刚走一步，他就把你唯一一条生路给堵死了，你不就死了吗。
度数为 2 的情况：
度数为 1 自然是不可能的。
然后好像就做完了？绷不住了
AC代码
AC
https://codeforces.com/gym/106262/submission/365635347
源代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
void Solve() {
ll N,M;
cin >> N >> M;
vector<vector<ll>> g(N+2);
for (int i=1;i<=M;++i) {
ll u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
ll ans=0;
for (int u=1;u<=N;++u) {
if (SZ(g[u])>=4) {
ans++;
continue;
}
if (SZ(g[u])==3) {
set<ll> st(all(g[u]));
st.insert(u);
ll cnt=0;
for (auto to:g[u]) {
for (auto toto:g[to]) {
if (!st.contains(toto)) {
++cnt;
break;
}
}
}
if (cnt>=2) {
++ans;
}
}else if (SZ(g[u])==2) {
set<ll> st(all(g[u]));
st.insert(u);
ll cnt=0;
for (auto to:g[u]) {
ll not_in_st=0;
for (auto toto:g[to]) {
if (!st.contains(toto)) {
++not_in_st;
}
if (not_in_st>=2) {
++cnt;
break;
}
}
}
if (cnt>=2) {
++ans;
}
}
}
cout<<ans<<'\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf);
#endif
Solve();
return 0;
}
|
心路历程（WA，TLE，MLE……）