目录
通信网络（csp201709-4） ：
问题描述
题目简述
某国的军队由N个部门组成，为了提高安全性，部门之间建立了M条通路，每条通路只能单向传递信息，即一条从部门a到部门b的通路只能由a向b传递信息。信息可以通过中转的方式进行传递，即如果a能将信息传递到b，b又能将信息传递到c，则a能将信息传递到c。一条信息可能通过多次中转最终到达目的地。
由于保密工作做得很好，并不是所有部门之间都互相知道彼此的存在。只有当两个部门之间可以直接或间接传递信息时，他们才彼此知道对方的存在。部门之间不会把自己知道哪些部门告诉其他部门。
现在请问，有多少个部门知道所有N个部门的存在。或者说，有多少个部门所知道的部门数量（包括自己）正好是N。
输入/输出格式
输入格式：
输入的第一行包含两个整数N, M，分别表示部门的数量和单向通路的数量。所有部门从1到N标号。
接下来M行，每行两个整数a, b，表示部门a到部门b有一条单向通路。
输出格式：
输出一行，包含一个整数，表示答案。
样例
输入样例：
4 4
1 2
1 3
2 4
3 4
输出样例：
2
问题分析
解题思路
首先，我看完之后第一个想到的就是floyd算法，类似于求传递闭包的问题。但是，看到后40%是n<=1000，就放弃了，顶多60分。之后发现，i，j相互知道对方存在只需要判断是否存在从i到j的道路和从j到i的道路就可以了。这样，只需要用dfs或者bfs遍历就可以求出了。因此，思路是求出原图和转置图中每个点的bfs的结果，看在两种图中能到达点的个数之和是否为n即可。
参考代码
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
class edge
{
public:
int from;
int to;
edge(int a,int b)
{
from=a;
to=b;
}
};
vector<int> points1[1010];
vector<int> points2[1010];
vector<edge> edges;
queue<int> q;
int vis1[1010][1010];
int vis2[1010][1010];
int n,m;
void init()
{
edges.clear();
memset(vis1,0,sizeof(vis1));
memset(vis2,0,sizeof(vis2));
for(int i=0;i<1010;i++)
{
points1[i].clear();
points2[i].clear();
}
}
void addedge(int a,int b)
{
edge e1(a,b);
edges.push_back(e1);
points1[a].push_back(edges.size()-1);
edge e2(b,a);
edges.push_back(e2);
points2[b].push_back(edges.size()-1);
}
void bfs1(int start)
{
while(!q.empty()) q.pop();
q.push(start);
while(!q.empty())
{
int index=q.front();
q.pop();
if(vis1[start][index]==1) continue;
vis1[start][index]=1;
for(int i=0;i<points1[index].size();i++)
{
edge te=edges[points1[index][i]];
if(vis1[start][te.to]==0)
{
q.push(te.to);
}
}
}
}
void bfs2(int start)
{
while(!q.empty()) q.pop();
q.push(start);
while(!q.empty())
{
int index=q.front();
q.pop();
if(vis2[start][index]==1) continue;
vis2[start][index]=1;
for(int i=0;i<points2[index].size();i++)
{
edge te=edges[points2[index][i]];
if(vis2[start][te.to]==0)
{
q.push(te.to);
}
}
}
}
int main()
{
init();
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
addedge(a,b);
}
for(int i=1;i<=n;i++)
{
bfs1(i);
bfs2(i);
}
int ans=0;
for(int i=1;i<=n;i++)
{
int cnt=0;
for(int j=1;j<=n;j++)
{
if(vis1[i][j]==1||vis2[i][j]==1) cnt++;
}
if(cnt==n) ans++;
}
printf("%d",ans);
return 0;
}
心得体会
这题稍微有点坑的地方是不能保证图中没有环路。因此必须在原图和转置图中都求bfs。虽然很快就发现了这点，但是被坑的感觉还是好烦。。。