题目描述
输入
5 2 4 3 0 4 5 0 0 0 1 0
输出
1 2
题意与思路:
A—>B,但B–/->A说明是个有向图.
子任务A:求需要收到新软件的学校数量.也就是说只要我们给这几个发了,那么其他学校也都能收到.
解决:先利用Tarjan求出连通分量,然后对其进行缩点,之后统计每个缩点的入度.入度为0,则说明必须向这个连通分量中发一个.求强连通分量缩点后入度为0的个数即为所求.
子任务B:发送到任意学校,该软件都可覆盖整个网络,说明要把这个网络构建成一个强连通图.题目是求添加扩展边的数目.
解决:先利用Tarjan求出连通分量,然后对其进行缩点,之后统计每个缩点的入度,出度.对于入度为0的缩点我们需要添加个入度边(不然软件谁传进来呢?);对于出度为0的缩点,我们需要添加一个出度边(总不能传到这里就死了吧.啊呜~~~) ,题目的意思是求最少的,所以我们可以把一条边添加在入度为0和出度为0的点之间,这样添加一条边,就解决了两个缩点. 程序中我们我们需要的边数: max(ans1,ans2)//ans1,ans2分别为入度,出度的缩点数量
最后注意一下当连通分量(缩点)为1时,子任务A只需要发送到1个学校,子任务B我们不需要添加其他边了.
图解
算法设计
参考代码
#include<iostream> #include<stack> #include<string.h> using namespace std; const int maxn = 100+10; int n,m,num,cnt,id,head[maxn],ins[maxn],low[maxn],dfn[maxn],belong[maxn],in[maxn],out[maxn]; stack<int> s; struct Edge{ int to,next; }e[maxn*maxn]; void add(int u,int v){ e[++num].next = head[u]; e[num].to = v; head[u] = num; } void Tarjan(int u){ low[u] = dfn[u] = ++cnt; s.push(u); ins[u] = 1; for(int i = head[u]; i; i = e[i].next){ int v = e[i].to; if(!dfn[v]){ Tarjan(v); low[u] = min(low[u],low[v]); }else if(ins[v]){ low[u] = min(low[u],low[v]); } } if(low[u]==dfn[u]){ int v; id++; do{ v = s.top(); s.pop(); ins[v] = 0; belong[v]=id;//为连通分量标号 }while(u!=v); } } void solveDegree(){//求每个连通分量的入度,出度 for(int u = 1; u <= n; u++){//遍历每条边. 求度 for(int i = head[u]; i; i = e[i].next){ int v = e[i].to; if(belong[u]!=belong[v]){//中间可能还有平行边呢.. 不过不用想那么多. out[belong[u]]++; in[belong[v]]++; } } } } int main() { int v; cin>>n;//5 for(int u = 1; u <= n; u++){ while(cin>>v&&v){ add(u,v); } } for(int i = 1; i<=n; i++){ if(!dfn[i]){ Tarjan(i); } } if(id==1){//强连通分量为1的特殊处理. cout<<1<<endl; cout<<0<<endl; return 0; } solveDegree(); int ans1=0,ans2=0;//统计入度为0的节点个数ans1 出度为0的节点个数ans2. for(int i = 1; i <= id; i++){//统计缩点中入度和出度为1的数量. 这里最多有id个哦. if(!in[i]){ ans1++; } if(!out[i]){ ans2++; } } cout<<ans1<<endl; cout<<max(ans1,ans2)<<endl; return 0; }
