关于bfs，连通分量， 拓扑排序
六度空间
image.png
输入样例 :
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
输出样例 :
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%
这道bfs很简单，如果dfs的话，不能直接用vis标记访问，而得用degree，比较麻烦，据说还会超时。。。
#include<bits/stdc++.h>
using namespace std;
static const int BLACK = 1;
typedef pair<int, int > P;
int color[10010];
vector <int> a[10010];
int main(){
int N, M, u, v;
cin >> N >> M;
while(M--){
cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
for(int i = 1; i <= N; i++){
queue <P > q;
int cnt = 1;
memset(color, 0, sizeof(color));
color[i] = BLACK;
q.push(make_pair(i, 6));
while(!q.empty()){
P x = q.front(); q.pop();
int t = x.first;
if(!x.second) continue;
for(int i = 0; i < a[t].size(); i++){
int k = a[t][i];
if(color[k]) continue;
color[k] = BLACK;
cnt++;
q.push(make_pair(k, x.second - 1));
}
}
printf("%d: %.2lf%\n", i, 100.0 * cnt / N);
}
return 0;
}
红色警报
image.png
输入样例：
5 4
0 1
1 3
3 0
0 4
5
1 2 0 4 3
输出样例：
City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
Game Over.
这道题我最开始拿到也是一脸懵逼，但知道连通分量这个概念后就很容易了。
image.png
题意即为判断每次攻占一个城市后连通分量是否增加。注意是和上一次（last）比较，比较完后要更新上一次（last = now）。
color数组用来标志是否被攻占（BLACK）或者是否访问过（GRAY）。注意每次计算完连通分量个数后要把GRAY还原成WHITE。
最后读题要仔细，Game Over是在失去最后一个城市后才输出
#include<bits/stdc++.h>
using namespace std;
static const int BLACK = 1;
static const int GRAY = -1;
static const int WHITE = 0;
vector <int > a[510];
int N, color[510];
int cul(int );
int main(){
int M, u, v, K, last, now, t;
cin >> N >> M;
while(M--){
cin >> u >> v;
a[v].push_back(u); a[u].push_back(v);
}
cin >> K;
last = cul(N);
while(K--){
cin >> t;
now = cul(t);
if(now > last) cout << "Red Alert: City " << t << " is lost!" << endl;
else cout << "City " << t << " is lost." << endl;
last = now;、、更新上一次
}
if(last == 0)// 读题仔细！！！
cout << "Game Over." << endl;
return 0;
}
int cul(int t){
color[t] = BLACK;
int cnt = 0;
for(int i = 0; i < N; i++){
if(color[i]) continue;
queue <int> q;
q.push(i);
color[i] = GRAY;
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = 0; i < a[u].size(); i++){
int v = a[u][i];
if(!color[v]){
q.push(v); color[v] = GRAY;
}
}
}
cnt++;
}
for(int i = 0; i < N; i++)//还原WHITE
if(color[i] == GRAY) color[i] = WHITE;
return cnt;
}
任务调度的合理性
image.png
输入样例1:
12
0
0
2 1 2
0
1 4
1 5
2 3 6
1 3
2 7 8
1 7
1 10
1 7
输出样例1:
1
输入样例2:
5
1 4
2 1 4
2 2 5
1 3
0
输出样例2:
0
判断是否成环，用拓扑排序。
image.png
#include<bits/stdc++.h>
using namespace std;
int d[110];//入度
vector <int > v[110];
queue <int > q;
int main(){
int N, K, u, cnt = 0;
cin >> N;
for(int i = 1; i <= N; i++){
cin >> K;
d[i] = K;
while(K--){
cin >> u;
v[u].push_back(i);
}
}
for(int i = 1; i <= N; i++)
if(d[i] == 0) q.push(i);
while(!q.empty()){
u = q.front(); q.pop(); cnt++;
for(int i = 0; i < v[u].size(); i++){
int t = v[u][i];
d[t]--;
if(d[t] == 0) q.push(t);
}
}
cout << ((cnt == N) ? "1" : "0") << endl;
return 0;
}
