USACO network of school 强连通分量

　　这个题的意思是有一个有向图， 每个顶点可以发送软件到与其相连的顶点上， 现在问1，至少发送给几个顶点能满足所有顶点都收到软件， 2：如果想让这个图变成强连通图，至少添几条边。  特例是给定的图是一个强连通图的话答案是1， 0. 一般情况下我们先将这个图的强连通分量求出来缩成一个点然后统计入度为0的点和出度为0的点的个数， 答案一就是入度为0的点的个数， 答案就是他们两个之间的最大值。代码如下：

/*ID: m1500293LANG: C++PROG: schlnet */ #include <cstdio> #include <cstring> #include <algorithm> #include <vector>using namespace std; const int max_v = 120;struct Scc {int V; //图的顶点数vector<int> G[max_v]; //原始图vector<int> rG[max_v]; //反向边的图vector<int> vs; //后序遍历顶点列表bool used[max_v]; //访问标记int cmp[max_v]; //所属强连通分量的拓扑排序void init(){for(int i=0; i<=V; i++) G[i].clear(), rG[i].clear();}void add_edge(int from, int to){G[from].push_back(to);rG[to].push_back(from);}void dfs(int v){used[v] = true;for(int i=0; i<G[v].size(); i++)if(!used[G[v][i]]) dfs(G[v][i]);vs.push_back(v);}void rdfs(int v, int k){used[v] = true;cmp[v] = k;for(int i=0; i<rG[v].size(); i++)if(!used[rG[v][i]]) rdfs(rG[v][i], k);}int scc(){memset(used, 0, sizeof(used));vs.clear();for(int v=1; v<=V; v++)if(!used[v]) dfs(v);memset(used, 0, sizeof(used));int k = 1;for(int i=vs.size()-1; i>=0; i--)if(!used[vs[i]]) rdfs(vs[i], k++);return k-1;} }ss; int num; //强连通分量的个数 int in[110], out[110]; int main() {freopen("schlnet.in", "r", stdin);freopen("schlnet.out", "w", stdout);int N;scanf("%d", &N);ss.V = N;ss.init();for(int i=1; i<=N; i++){int t;scanf("%d", &t);while(t != 0){ss.add_edge(i, t);scanf("%d", &t);}} // printf("%d\n", ss.scc());num = ss.scc();if(num == 1){printf("1\n0\n");return 0;}for(int u=1; u<=N; u++) //u->vfor(int j=0; j<ss.G[u].size(); j++){int v = ss.G[u][j];int uu=ss.cmp[u], vv=ss.cmp[v];if(uu != vv){in[vv]++;out[uu]++;}}int in_0_num=0, out_0_num=0;for(int i=1; i<=num; i++){if(!in[i]) in_0_num++;if(!out[i]) out_0_num++;}printf("%d\n%d\n", in_0_num, max(in_0_num, out_0_num));return 0; }

 

转载于:https://www.cnblogs.com/xingxing1024/p/5180641.html

总结

以上是生活随笔为你收集整理的USACO network of school 强连通分量的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。