codeforce_exercise_r27

目录

通信网络(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。虽然很快就发现了这点,但是被坑的感觉还是好烦。。。

上一篇:codeforce_exercise_r21


下一篇:中职网安 命令注入 笔记