题目描述
D D D 市有 n n n 个公交车站和 m m m 条公交线路,公交车站的编号为从 1 1 1到 n n n 。每条公交线路会经过某些车站,如果两条公交线路有公共的公交车站,那么它们可以在公共车站相互换乘。比如线路 ( 1 , 2 , 3 , 9 ) (1,2,3,9) (1,2,3,9) 和线路 ( 2 , 4 , 5 , 7 , 9 ) (2,4,5,7,9) (2,4,5,7,9) 可以在 2 2 2 号车站或 9 9 9 号车站相互换乘。
从一个公交车站出发,乘客可以选择经过此站的任意公交线路运往线路上任意其他车站,还可以在下车后换乘其他线路到达其他车站,然后可以继续换乘……
小红想知道在所有 n ∗ ( n − 1 ) / 2 n*(n-1)/2 n∗(n−1)/2 对公交车站中,有多少对是相互不可达的?
输入格式
第一行是两个正整数 n n n 、 m m m ( 2 ≤ n ≤ 100 2≤n≤100 2≤n≤100 , 1 ≤ m ≤ 1000 1≤m≤1000 1≤m≤1000 )。
接下来m行,每行首先是一个整数 c i c_i ci( 2 ≤ c i ≤ n 2≤c_i≤n 2≤ci≤n),接下来是 c i c_i ci 个大小在 1 1 1 到 n n n 之间的互不相同的整数,表示一条公交线路。
输出格式
仅一行,是一个整数,表示有多少对相互不可达的公交车站。
样例 #1
样例输入 #1
3 1
2 1 2
样例输出 #1
2
样例输入 #2
10 4
4 1 2 3 6
3 2 4 5
3 2 4 7
3 8 9 10
样例输出 #2
21
提示:
样例1中,只有一条公交线路 ( 1 , 2 ) (1,2) (1,2) ,相互不可达的有 ( 1 , 3 ) (1,3) (1,3) 、 ( 2 , 3 ) (2,3) (2,3) 两对。
样例 2 2 2 中,有 4 4 4 条公交线路,相互不可达的车站共有 21 21 21 对。
题目分析
本题考查图的连通性问题,我们可以使用 DFS 或 BFS 对图进行遍历来求连通块的个数。
不难发现,如果一个点在一次 DFS 中被访问过,那么这个点所在的连通块中的所有点都会被访问到。因此,我们只需要对每个未访问的点进行 DFS,记录连通块的个数即可。
在 DFS 中,我们可以从当前结点出发,遍历其所有相邻结点,并将这些相邻结点标记为已访问。遍历完所有相邻结点后,递归遍历每个相邻结点即可。
代码实现
我们可以使用邻接表来储存公交车站之间的关系,然后使用 DFS 来遍历所有连通块。
下面是使用 C++ 实现的代码:
#include <iostream>
#include <vector>using namespace std;const int N = 110;int n, m;
vector<int> g[N]; // 存储公交线路信息
bool visited[N]; // 存储是否访问过该车站void dfs(int u) // 进行深度优先搜索
{visited[u] = true; // 标记该车站已被访问for (auto v : g[u]) // 遍历该车站的所有相邻车站if (!visited[v]) // 如果该相邻车站未被访问,则继续深度搜索dfs(v);
}int main()
{cin >> n >> m;for (int i = 0; i < m; i++){int cnt;cin >> cnt;vector<int> line(cnt);for (int j = 0; j < cnt; j++){cin >> line[j];}for (int j = 0; j < cnt; j++)for (int k = j + 1; k < cnt; k++) // 将每条公交线路上的车站进行两两连接{g[line[j]].push_back(line[k]);g[line[k]].push_back(line[j]);}}int ans = 0;for (int i = 1; i <= n; i++) // 枚举所有车站,进行深度优先搜索{fill(visited, visited + N, false); // 每次搜索前将所有车站的访问状态初始化为未访问dfs(i);for (int j = i + 1; j <= n; j++)if (!visited[j]) // 如果某个车站未被搜索到,则该车站与其它车站是不可达的ans++;}cout << ans << endl;return 0;
}