This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

Problem Set Master Index Study reference blog: Graphs

06-Graph 1 List Connected Sets (25 pts)

Problem link

Very basic training, a must-do

Problem Summary

Output all connected sets in the graph. First output the DFS results, then the BFS results.

Code

#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;
}

Test Cases

Test cases are as follows:

06-Graph 2 Saving James Bond - Easy Version (25 pts)

Problem link

Poor 007 is waiting for you to save him. It’s up to you now.

Code

#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;
}

Test Cases

Test cases are as follows:

06-Graph 3 Six Degrees of Separation (30 pts)

Problem link

After listening to the lecture, the approach for this problem should be fairly clear, but the implementation still requires a decent amount of code. Give it a try if you have time.

Problem Summary

Given a social network graph, calculate the percentage of nodes that satisfy the “Six Degrees of Separation” theory for each node.

Code

#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;
}

Test Cases

Test cases are as follows: