題目集總目錄
學習指路部落格 圖

06-圖1 列出連通集 (25分)

本題鏈接

非常基礎的訓練，一定要做

題目大意

輸出圖中所有連通集。先輸出DFS的結果，再輸出BFS的結果。

程式碼

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn = 11;
int N,E,x,y;
bool visited[maxn];
int edge[maxn][maxn];
queue<int> q;
void DFS(int v) {
    visited[v] = true;
    printf(" %d", v);
    for(int i = 0; i < N; ++i) {
        if(!visited[i] && edge[v][i] == 1) 
            DFS(i);
    }
}
void BFS(int v) {
    q.push(v);
    while(!q.empty()) {
        v = q.front();
        q.pop();
        if(visited[v]) continue;
        visited[v] = true;
        printf(" %d", v);
        for(int i = 0; i < N; ++i) {
            if(!visited[i] && edge[v][i] == 1) 
                q.push(i);
        }
    }
}
int main(){
    scanf("%d %d", &N, &E);
    for(int i = 0; i < E; ++i) {
        scanf("%d %d", &x, &y);
        edge[x][y] = edge[y][x] = 1;
    }
    for(int i = 0; i < N; ++i) visited[i] = false;
    for(int i = 0; i < N; ++i) {
        if(!visited[i]){
            printf("{");
            DFS(i);
            printf(" }\n");
        }
    }
    for(int i = 0; i < N; ++i) visited[i] = false;
    for(int i = 0; i < N; ++i) {
        if(!visited[i]){
            printf("{");
            BFS(i);
            printf(" }\n");
        }
    }
    return 0;
}

測試點

測試點如下

06-圖2 Saving James Bond - Easy Version (25分)

本題鏈接

可憐的007在等着你拯救，你……看着辦哈；

程式碼：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int maxn = 105;
int N,D;
bool visited[maxn];
int edge[maxn][maxn];
struct Point {
    int x, y;
    bool visited;
} v[maxn],s;
double countDist(Point a, Point b) {
    return sqrt(pow((a.x-b.x),2) + pow((a.y-b.y),2));
}
bool check(Point a) {
    int s = 50 - D;
    if(abs(a.x) >= s || abs(a.y) >= s) 
        return true;
    else return false;
}
bool DFS(int i) {
    bool ans = false;
    v[i].visited = true;
    if(check(v[i])) {
        return true;
    } else {
        for(int j = 0; j < N; ++j) {
            if(!v[j].visited && countDist(v[i],v[j]) <= 1.0*D) {
                ans = DFS(j);
                if(ans) break;
            }
        }
    }
    return ans;
}
bool firstJump(int i) {
    double d = countDist(s,v[i]);
    d -= 7.5;
    return d <= D;
}
bool Save007() {
    bool ans = false;
    for(int i = 0; i < N; ++i) {
        if(!v[i].visited && firstJump(i)) {
            ans = DFS(i);
            if(ans) break;
        }
    }
    return ans;
}
int main(){
    scanf("%d %d", &N, &D);
    s.visited = false;
    s.x = s.y = 0;
    for(int i = 0; i < N; ++i) {
        scanf("%d %d", &v[i].x, &v[i].y);
        v[i].visited = false;
    }
    if(Save007()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

測試點

測試點如下

06-圖3 六度空間 (30分)

本題鏈接

在聽完課以後，這題的思路應該比較清晰了，不過實現起來還是頗有碼量的，有時間就嘗試一下。

題目大意

給你一個社羣網路圖，請你對每個節點計算符合「六度空間」理論的結點佔結點總數的百分比。

程式碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 1005;
int N,M,x,y;
bool visited[maxn];
int edge[maxn][maxn];
int BFS(int v) {
    queue<int> q;
    int cnt = 1;
    int level = 0;
    int last = v;
    int now;
    visited[v] = true;
    q.push(v);
    while(!q.empty()) {
        v = q.front();
        q.pop();
        for(int i = 1; i <= N; ++i) {
            if(!visited[i] && edge[v][i] == 1) {
                q.push(i);
                visited[i] = true;
                cnt++;
                now = i;
            }
        }
        if(v == last) {
            level++;
            last = now;
        }
        if(level == 6) break;
    }
    return cnt;
}
int main(){
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= M; ++i) {
        scanf("%d %d", &x, &y);
        edge[x][y] = edge[y][x] = 1;
    }
    for(int i = 1; i <= N; ++i) {
        memset(visited, 0, sizeof(visited));
        double ratio = BFS(i) * 1.0 / N;
        printf("%d: %.2f%\n",i,ratio * 100.0);
    }
    return 0;
}

測試點

測試點如下