Network of Schools（强联通）

2023-10-08 04:32

文章标签 network schools 联通

本文主要是介绍Network of Schools（强联通），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

思路

n个学校，给出每个学校可以联通的学校
求入度为0的点有多少个，和入度为0与出度为0较多的一个

代码

#include<stdio.h>
#include<string.h>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
#define N 110
vector<int>edge[N];
stack<int>s;
int low[N],dfn[N],vis[N];
int f[N],F[N],num[N]; //入度，出度，所属强联通分量编号
int k=0,l=0;void tarjian(int u)
{low[u]=dfn[u]=++k;s.push(u);vis[u]=1;for(int i=0;i<edge[u].size();i++){int v=edge[u][i];if(!dfn[v]){tarjian(v);low[u]=min(low[u],low[v]);}else if(vis[v])low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]){++l;while(1){int x=s.top();s.pop();vis[x]=0;num[x]=l;if(u==x) break;}}return;
}
int main()
{int n,t;scanf("%d",&n);for(int i=1;i<=n;i++)while(~scanf("%d",&t)&&t)edge[i].push_back(t);for(int i=1;i<=n;i++) //莫要忘记！！！if(!dfn[i])tarjian(i);if(l==1){printf("1\n0\n"); //本身就是强联通分量的图，直接输出return 0;}int x=0,y=0,v;for(int i=1;i<=n;i++) //n个节点for(int j=0;j<edge[i].size();j++){v=edge[i][j]; //与第i点相连的第j个点，vif(num[i]!=num[v]) //若i点和P点不在一个分量内，说明i->vf[num[v]]=1; //v点入度为1F[num[i]]=1; //i点出度为1}//l个强联通分量for(int i=1;i<=l;i++){if(f[i]==0)x++;     //找入度为0的点if(F[i]==0)y++;     //出度为0的带你}printf("%d\n%d\n",x,x>y?x:y);return 0;
}