第六講圖（上）_ZenDei技術網路在線

06 圖1：列出連通集. Description: 給定一個有N個頂點和E條邊的無向圖，請用DFS和BFS分別列出其所有的連通集。假設頂點從0到N 1編號。進行搜索時，假設我們總是從編號最小的頂點出發，按編號遞增的順序訪問鄰接點。 Input: 輸入第1行給出2個整數N(0, 10)和E，分別是圖的 ...

06-圖1：列出連通集.

Description:

給定一個有N個頂點和E條邊的無向圖，請用DFS和BFS分別列出其所有的連通集。假設頂點從0到N-1編號。進行搜索時，假設我們總是從編號最小的頂點出發，按編號遞增的順序訪問鄰接點。

Input:

輸入第1行給出2個整數N(0, 10)和E，分別是圖的頂點數和邊數。隨後E行，每行給出一條邊的兩個端點。每行中的數字之間用1空格分隔。

Output:

按照"{v1, v2..., vk}"的格式，每行輸出一個連通集。先輸出DFS的結果，再輸出BFS的結果。

SampleInput:

8 6
0 7
0 1
2 0
4 1
2 4
3 5

SampleOutput:

{ 0 1 4 2 7 }
{ 3 5 }
{ 6 }
{ 0 1 2 7 4 }
{ 3 5 }
{ 6 }

Codes:

//#define LOCAL

#include <cstdio>
#include <queue>
using namespace std;

#define M 10
int ne, nv, check[M], g[M][M];

void bG() {
    int i, v1, v2;
    scanf("%d%d", &nv, &ne);
    for(i=0; i<ne; ++i) {
        scanf("%d%d", &v1, &v2);
        g[v1][v2] = g[v2][v1] = 1;
    }
}

int cV() {
    int i;
    for(i=0; i<nv; ++i) 
        if(!check[i]) break;
    if(i == nv) return -1;
    return i;
}

void cC() { for(int i=0; i<nv; ++i) check[i] = 0; }

int BFS() {
    int i, j; queue<int> q;
    i = cV();
    if(i == -1) return i; 
    q.push(i); check[i] = 1;
    printf("{ %d ", i);
    while(!q.empty()) {
        int t = q.front(); q.pop();
        for(j=0; j<nv; ++j) 
            if(g[t][j]==1 && !check[j]) {
                check[j] = 1; printf("%d ", j);
                q.push(j);
            }
    }
    printf("}\n"); return BFS();
}

void DFS(int vi) {
    check[vi] = 1;
    printf("%d ", vi);
    for(int j=0; j<nv; ++j)
        if(g[vi][j]==1 && !check[j]) DFS(j);
}

int listDFS() {
    if(cV() == -1) return -1; printf("{ ");
    DFS(cV()); printf("}\n");
    return listDFS();
}

int main()
{
    #ifdef LOCAL
        freopen("E:\\Temp\\input.txt", "r", stdin);
        freopen("E:\\Temp\\output.txt", "w", stdout);
    #endif

    bG(); listDFS(); cC(); BFS();

    return 0;
}

06-圖2：Saving James Bond - Easy Version.

Description:

This time let us consider the situation in the movie "Live and Let Die" in which James Bond, the world's most famous spy, was captured by a group of drug dealers. He was sent to a small piece of land at the center of a lake filled with crocodiles. There he performed the most daring action to escape -- he jumped onto the head of the nearest crocodile! Before the animal realized what was happening, James jumped again onto the next big head... Finally he reached the bank before the last crocodile could bite him (actually the stunt man was caught by the big mouth and barely escaped with his extra thick boot).

Assume that the lake is a 100 by 100 square one. Assume that the center of the lake is at (0,0) and the northeast corner at (50,50). The central island is a disk centered at (0,0) with the diameter of 15. A number of crocodiles are in the lake at various positions. Given the coordinates of each crocodile and the distance that James could jump, you must tell him whether or not he can escape.

Input:

Each input file contains one test case. Each case starts with a line containing two positive integers N(<=100), the number of crocodiles, and D, the maximum distance that James could jump. Then N lines follow, each containing the (x, y)(x,y) location of a crocodile. Note that no two crocodiles are staying at the same position.

Output:

For each test case, print in a line "Yes" if James can escape, or "No" if not.

SampleInput1:

14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12

SampleOutput1:

Yes

SampleInput2:

4 13
-12 12
12 12
-12 -12
12 -12

SampleOutput2:

Codes:

//#define LOCAL

#include <cstdio>
#include <cmath>

struct C { double x, y; };

int rC(double d, C p) { return (15+d)*(15+d)>=p.x*p.x+p.y*p.y; }
int rBe(double d, C p1, C p2) { return d*d>=(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y); }
int rBa(double d, C p) {return p.x<=-50+d||p.x>=50-d||p.y>=50-d||p.y<=d-50;}
int DFS(double d, C *cr, int v, int *vi, int n) {
    if(rBa(d, cr[v])) return 1;
    for(int i=0; i<n; ++i) 
        if(!vi[i] && rBe(d, cr[v], cr[i])) {
            vi[i] = 1;
            if(DFS(d, cr, i, vi, n)) return 1;
    }
    return 0;
}

int main()
{
    #ifdef LOCAL
        freopen("E:\\Temp\\input.txt", "r", stdin);
        freopen("E:\\Temp\\output.txt", "w", stdout);
    #endif

    int i, n, f = 0, vi[100] = {}; double d;
    scanf("%d%lf", &n, &d);
    if(d >= 35) { printf("Yes\n"); return 0; }
    C cr[102];
    for(i=0; i<n; ++i) scanf("%lf%lf", &cr[i].x, &cr[i].y);

    for(i=0; i<n; ++i) 
        if(!vi[i] && rC(d, cr[i])) {
            vi[i] = 1;
            if(DFS(d, cr, i, vi, n)) { printf("Yes\n"); f = 1; break; }
        }
    if(!f) printf("No\n");

    return 0;
}

06-圖3：六度空間.

Description:

“六度空間”理論又稱作“六度分隔（Six Degrees of Separation）”理論。這個理論可以通俗地闡述為：“你和任何一個陌生人之間所間隔的人不會超過六個，也就是說，最多通過五個人你就能夠認識任何一個陌生人。”如圖1所示。“六度空間”理論雖然得到廣泛的認同，並且正在得到越來越多的應用。但是數十年來，試圖驗證這個理論始終是許多社會學家努力追求的目標。然而由於歷史的原因，這樣的研究具有太大的局限性和困難。隨著當代人的聯絡主要依賴於電話、簡訊、微信以及網際網路上即時通信等工具，能夠體現社交網路關係的一手數據已經逐漸使得“六度空間”理論的驗證成為可能。

假如給你一個社交網路圖，請你對每個節點計算符合“六度空間”理論的結點占結點總數的百分比。

Input:

輸入第1行給出兩個正整數，分別表示社交網路圖的結點數N(1<N<=1000，表示人數）、邊數M（<=33×N，表示社交關係數）。隨後的M行對應M條邊，每行給出一對正整數，分別是該條邊直接連通的兩個結點的編號（節點從1到N編號）。

Output:

對每個結點輸出與該結點距離不超過6的結點數占結點總數的百分比，精確到小數點後2位。每個結節點輸出一行，格式為“結點編號:（空格）百分比%”。

SampleInput:

10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

SampleOutput:

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%

Codes:

//#define LOCAL

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

#define M 100010
int m, n, vi[M];
vector<int> v[M];

int sds(int t) {
    queue<int> q; q.push(t); vi[t] = 1;
    int i, cN = 0, lN = 1, l = 0, cnt = 1;
    while(!q.empty()) {
        t = q.front(); q.pop(); --lN;
        for(i=0; i<v[t].size(); ++i) {
            if(!vi[v[t][i]]) {
                vi[v[t][i]] = 1; 
                q.push(v[t][i]); ++cN;
            }
        }
        if(!lN) {
            lN = cN; cN = 0;
            cnt += lN; ++l;
        }
        if(l == 6) break;
    }
    return cnt;
}


int main() {
    #ifdef LOCAL
        freopen("E:\\Temp\\input.txt", "r", stdin);
        freopen("E:\\Temp\\output.txt", "w", stdout);
    #endif

    int i, f, t, cnt;
    scanf("%d%d", &n, &m);
    while(m--) {
        scanf("%d%d", &f, &t);
        v[f].push_back(t); v[t].push_back(f);
    }

    for(i=1; i<=n; ++i) {
        cnt = sds(i);
        memset(vi, 0, sizeof(vi));
        printf("%d: %.2f%%\n", i, cnt*100.0/n);
    } 

    return 0;
}

第六講 圖（上）

06-圖1：列出連通集.

Description:

Input:

Output:

SampleInput:

SampleOutput:

Codes:

06-圖2：Saving James Bond - Easy Version.

Description:

Input:

Output:

SampleInput1:

SampleOutput1:

SampleInput2:

SampleOutput2:

Codes:

06-圖3：六度空間.

Description:

Input:

Output:

SampleInput:

SampleOutput:

Codes:

第六講圖（上）