題目描述
在神秘的幻想?陸中，存在著?n?個古老而神奇的迷宮，迷宮編號從?1?到?n。有的迷宮之間可以直接往返，有的可以?到別的迷宮，但是不能?回來。玩家小楊想挑戰?下不同的迷宮，他決定從?m?號迷宮出發。現在，他需要你幫助他統計：有多少迷宮可以直接到達?m?號迷宮，m?號迷宮可以直接到達其他的迷宮有多少，并求出他們的和。
需要注意的是，對于?i?(1≤i≤n) 號迷宮，它總可以直接到達自身。
輸入格式
第一行兩個整數?n?和?m，分別表示結點迷宮總數，指定出發迷宮的編號。
下面?n?行，每行?n?個整數，表示迷宮之間的關系。對于第?i?行第?j?列的整數，1?表示能從?i?號迷宮直接到達?j?號迷宮，0?表示不能直接到達。
輸出格式
一行輸出空格分隔的三個整數，分別表示迷宮?m?可以直接到達其他的迷宮有多少個，有多少迷宮可以直接到達?m?號迷宮，這些迷宮的總和。
輸入輸出樣例
輸入 #1
6 4 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1
輸出 #1
3 3 6
題目要求給出有向圖中可到達某節點的節點數與某節點可到達的節點數，我們可以用兩個共軛的鄰接表來存儲。
#include<bits/stdc++.h>
using namespace std;int main(){int n, m;cin>>n>>m;vector<vector<int>> mat(n+1); // 某節點能到達的節點的鄰接表vector<vector<int>> re_mat(n+1); // 能到達某節點的鄰接表for(int i = 1;i<=n;i++){for(int j = 1;j<=n;j++){int tmp;cin>>tmp;if(tmp){mat[i].push_back(j);re_mat[j].push_back(i);}}}int ans1, ans2, ans3;ans2 = re_mat[m].size();ans1 = mat[m].size();ans3 = ans1+ans2;cout<<ans1<<' '<<ans2<<' '<<ans3;return 0;
}
