AC题解

#include <iostream>
#include <cstring>
using namespace std;
const int MAX_RELATIONSHIPS = 100005;
struct RelationshipEdge {
    int to;     
    int next;   
} edges[MAX_RELATIONSHIPS << 1];
int vertices[MAX_RELATIONSHIPS];
int test_cases, num_relationships, microblog_id;
int edge_index, repost_count;
int follower, following;
int visited[10005];
void addEdge(int follower, int following) {
    edge_index += 1;
    edges[edge_index].to = following;
    edges[edge_index].next = vertices[follower];
    vertices[follower] = edge_index;
}
void dfs(int root) {
    int index = vertices[root];
    while (index != 0) {
        int to = edges[index].to;
        if (!visited[to]) {
            visited[to] = 1;
            repost_count += 1;
            dfs(to);
        }
        index = edges[index].next;
    }
}
int main() {
    cin >> test_cases;
    for (int i = 1; i <= test_cases; i++) {
        edge_index = 0;
        repost_count = 0;
        memset(visited, 0, sizeof visited);
        memset(vertices, 0, sizeof vertices);
        cin >> num_relationships >> microblog_id;
        for (int j = 1; j <= num_relationships; j++) {
            cin >> follower >> following;
            addEdge(following, follower);
        }
        visited[microblog_id] = 1;
        dfs(microblog_id);
        cout << "Case #" << i << ": " << repost_count << endl;
    }
    return 0;
}