#include <iostream> #include <vector> #include <queue> using namespace std; const int MAXV = 1000; const int INF = 1000000000; //下标代表点,数组元素代表连接的点 //图的邻接表 vector<int> Adj[MAXV]; //顶点数 int n; //DFS 如果顶点i已经被访问，则vis[i]=true,初始值为false bool vis[MAXV] = {false}; //BFS bool inq[MAXV] = { false }; //u:当前访问的顶点编号 //depth为深度 void DFS(int u,int depth) { //输出，并设置顶点已经被访问 cout << u ; vis[u] = true; for(int i=0;i<Adj[u].size();i++) { //与u相接的顶点 int v = Adj[u][i]; //如果没有被访问 if(vis[v] == false) { DFS(v,depth + 1); } } } //测试DFS int main1() { Adj[0].push_back(1); Adj[0].push_back(2); Adj[1].push_back(0); Adj[1].push_back(2); Adj[1].push_back(3); Adj[1].push_back(4); Adj[2].push_back(0); Adj[2].push_back(1); Adj[2].push_back(4); Adj[3].push_back(1); Adj[3].push_back(4); Adj[3].push_back(5); Adj[4].push_back(1); Adj[4].push_back(2); Adj[4].push_back(3); Adj[4].push_back(5); Adj[5].push_back(1); Adj[5].push_back(4); DFS(0,1); return 0; } //遍历单个连通块 void BFS(int u) { queue<int> q; q.push(u); inq[u] = true; while(!q.empty()) { int u = q.front(); cout << u ; q.pop(); for(int i=0;i<Adj[u].size();i++) { int v = Adj[u][i]; if(inq[v] == false) { q.push(v); inq[v] = true;//标记v为已被加入过队列 } } } } //遍历所有连通量 void BFSTrave() { for(int u=0;u<n;u++) { if(inq[u] == false) { BFS(u); } } } //BFS int main() { Adj[0].push_back(1); Adj[0].push_back(2); Adj[1].push_back(0); Adj[1].push_back(2); Adj[1].push_back(3); Adj[1].push_back(4); Adj[2].push_back(0); Adj[2].push_back(1); Adj[2].push_back(4); Adj[3].push_back(1); Adj[3].push_back(4); Adj[3].push_back(5); Adj[4].push_back(1); Adj[4].push_back(2); Adj[4].push_back(3); Adj[4].push_back(5); Adj[5].push_back(1); Adj[5].push_back(4); BFS(0); return 0; }
题目练习:PAT A1076 Forwards on Weibo
#include <stdio.h> #include <string.h> #include <vector> #include <queue> #include <iostream> using namespace std; const int MAXV = 1010; struct Node { int id; int layer; }; //邻接表 vector<Node> Adj[MAXV]; //是否被加入过队列 bool inq[MAXV] = {false}; //s为起始结点,L为层数上限 int BFS(int s,int L) { int numForward = 0;//转发数 queue<Node> q; Node start;//定义起始结点 start.id = s; start.layer = 0; q.push(start); inq[start.id] = true; while(!q.empty()) { //取出队首结点 Node topNode = q.front(); q.pop(); //取出队首结点的编号 int u = topNode.id; for(int i=0; i < Adj[u].size();i++) { Node next = Adj[u][i]; next.layer = topNode.layer + 1; //如果next的编号未被加入过队列,且next的层次不超过上限L if(inq[next.id] == false && next.layer <= L) { q.push(next); inq[next.id] = true; numForward++;//转发数加1 } } } return numForward; } int main() { Node user; //n为人数 L为层数 numFollow为关注的人数 idFollow为关注的人 int n,L,numFollow,idFollow; cin >> n >> L; for(int i=1;i<=n;i++) { user.id = i; cin >> numFollow; for(int j=0;j<numFollow;j++) { cin >> idFollow; //下标为点,元素为连接的点 Adj[idFollow].push_back(user); } } //numQuery为查询的个数 int numQuery,s; cin >> numQuery; for(int i=0;i<numQuery;i++) { memset(inq,false,sizeof(inq)); cin >> s; int numForward = BFS(s,L); cout << numForward << endl; } } |