先記錄某個點與哪些點有相連，然後對起點和TTL用BFS即可。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <queue> | |
| #include <map> | |
| #include <vector> | |
| using namespace std; | |
| map<int, int> mapping; | |
| struct node_type{ | |
| vector<int> connceted_node; | |
| }; | |
| int NC; | |
| int numOfnode; | |
| int BFS(int start_node, int TTL, node_type node[]); | |
| int main() | |
| { | |
| //freopen("input.txt","rt",stdin); | |
| int Case = 1; | |
| while (scanf("%d", &NC)) { | |
| if (!NC) break; | |
| node_type node[100]; | |
| mapping.clear(); | |
| int node1, node2, i, j; | |
| for (i=0, j=0; i<NC; ++i) { | |
| scanf("%d%d", &node1, &node2); | |
| if (mapping.find(node1) == mapping.end()) | |
| mapping[node1] = j++; | |
| if (mapping.find(node2) == mapping.end()) | |
| mapping[node2] = j++; | |
| node[mapping[node1]].connceted_node.push_back(mapping[node2]); | |
| node[mapping[node2]].connceted_node.push_back(mapping[node1]); | |
| } | |
| numOfnode = j; | |
| int TTL; | |
| while (scanf("%d%d", &node1, &TTL)) { | |
| if (!node1 && !TTL) break; | |
| int numOfNotReach = BFS(node1, TTL, node); | |
| printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n", | |
| Case++, numOfNotReach, node1, TTL); | |
| } | |
| } | |
| return 0; | |
| } | |
| int BFS(int start_node, int TTL, node_type node[]) | |
| { | |
| queue<int> Q; | |
| Q.push(mapping[start_node]); | |
| int visit[100] = {0}; | |
| visit[mapping[start_node]] = 1; | |
| int nOfReach = 1; | |
| while (!Q.empty()) { | |
| int cur = Q.front(); | |
| if (visit[cur] > TTL) return numOfnode - nOfReach; | |
| Q.pop(); | |
| for (int nxt : node[cur].connceted_node) { | |
| if(visit[nxt] == 0){ | |
| visit[nxt] = visit[cur] + 1; | |
| Q.push(nxt); | |
| ++nOfReach; | |
| } | |
| } | |
| } | |
| return numOfnode - nOfReach; | |
| } |
沒有留言:
張貼留言