题目大意
题目总结
给定一个无向图（无重边、无自环），你要给每条边指定一个方向，得到有向图。
定义一条点序列 v1,v2,…,vk（长度可任意大，点可重复）是“交替路径”，当且仅当相邻边方向按如下模式交替：
-
第 1 条边是 v1→v2；
-
第 2 条边是 v3→v2；
-
第 3 条边是 v3→v4；
-
第 4 条边是 v5→v4；
-
之后继续这样“顺、逆、顺、逆”交替。
一个点 v 被称为“beautiful”，如果在原图中所有从 v 出发的路径（不要求简单路径，允许重复点和边）在你定向后都满足上面的交替性质。
目标：对每个测试用例，求最多能让多少个点成为 beautiful。
输入输出要求（题意层面）
-
输入有多组测试。
-
每组给 n,m 和 m 条无向边。
-
需要输出一个整数：该组图中可成为 beautiful 的点数最大值。
样例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| Input
4
8 9
1 3
1 4
2 3
2 4
5 6
6 7
7 8
8 5
6 8
4 0
6 2
1 5
2 3
1 0
|
样例解释
-
第 1 组输出 2：最多只能让 2 个点满足“从该点出发的任意路径都交替”。
-
第 2 组输出 4：图中没有边，任意从点出发的路径都平凡成立，所以 4 个点都可 beautiful。
-
第 3 组输出 4：最多可让 4 个点满足条件。
-
第 4 组输出 1：只有 1 个点且无边，因此这个点可 beautiful。
思路讲解
AC代码
源代码
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
131
132
133
134
135
136
137
138
139
140
141
|
#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;
struct U_step{
ll u,step;
};
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);
}
vector<char> vis(N+2);
vector<char> color(N+2);
ll ans=0;
for (int i=1;i<=N;++i) {
if (vis[i]) {
continue;
}
queue<U_step> q;
q.push({i,1});
vis[i]=true;
color[i]=1;
vector<ll> cnt(2);
cnt[color[i]]++;
bool is_erfen=true;
while (!q.empty()) {
auto [u,step]=q.front();
q.pop();
for (auto v:g[u]) {
if (vis[v]) {
if (color[v]!=(step+1)%2) {
is_erfen=false;
}
continue;
}
vis[v]=1;
color[v]=(step+1)%2;
cnt[color[v]]++;
q.push({v,step+1});
}
}
if (!is_erfen) continue;
ans+=max(cnt[0],cnt[1]);
}
cout<<ans<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf);
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
|
心路历程（WA，TLE，MLE……）