首页 > 代码库 > POJ 2186-Popular Cows (图论-强联通分量Korasaju算法)

POJ 2186-Popular Cows (图论-强联通分量Korasaju算法)

题目链接:http://poj.org/problem?id=2186

题目大意:有n头牛和m对关系, 每一对关系有两个数(a, b)代表a牛认为b牛是“受欢迎”的,且这种关系具有传递性, 如果a牛认为b牛“受欢迎”, b牛认为c牛“受欢迎”, 那么a牛也认为c牛“受欢迎”。 现在想知道有多少头牛受除他本身外其他所有牛的欢迎?

解题思路:如果有两头或者多头牛受除他本身外其他所有牛的欢迎, 那么在这两头或者多头牛之中, 任意一头牛也受两头或者多头牛中别的牛的欢迎, 即这两头或者多头牛同属于一个强联通分量, 且其他强联通分量都可以到达该强联通分量。那么可以用Korasaju算法进行强联通分量的分解, 然后还能够得到各个强联通分量拓扑排序后的顺序, 那么唯一可以成为解的只有拓扑序最后的那个联通分量, 并且需要检查其他强联通分量是否能全部到达这个强联通分量, 如果能够全部可达, 那么该强联通分量有多少元素即为问题的解, 否则为0;

强联通分量的分解的步骤:

1:对于图G, 深度优先遍历G, 算出每个节点u结束的时间s[u], 起点如何选择无所谓。

2:对于图G的转置图rG, 选择遍历的起点时, 按照节点的结束时间从大到小进行, 遍历过程中, 一遍遍历, 一遍给节点做分类标记, 每找到一个新的起点, 分类标记加一

3:对于第二步骤中,每一个相同标记的点即为一个强联通分量

代码如下:

技术分享
#include<stdio.h>#include<string.h>#include<vector>#include<algorithm>using namespace std;const int N = 10003;vector<int>G[N], rG[N], vs;bool used[N];int v;int cmp[N];void add_edge(int a, int b){    G[a].push_back(b);    rG[b].push_back(a);}void dfs(int n){    used[n] = true;    for(int i=0; i<G[n].size(); ++ i)    {        int v = G[n][i];        if(used[v] == false)            dfs(v);    }    vs.push_back(n);}void rdfs(int n, int k){    used[n] = true, cmp[n] = k;    for(int i=0; i<rG[n].size(); ++ i)    {        int v=rG[n][i];        if(used[v] == false)            rdfs(v, k);    }}int scc(){    memset(used, false, sizeof(used));    vs.clear();    for(int i=0; i<v; ++ i)        if(used[i] == false)            dfs(i);    memset(used, false, sizeof(used));    int k=0;    for(int i=vs.size()-1; i>=0; -- i)    {        if(used[vs[i]] == false)            rdfs(vs[i], k++);    }    return k;}int main(){    int m;    scanf("%d%d", &v, &m);    for(int i=1; i<=m; ++ i)    {        int a, b;        scanf("%d%d", &a, &b);        add_edge(a-1, b-1);    }    int n = scc();    int u = 0, num = 0;    for(int i=0; i<v; ++ i)        if(cmp[i] == n-1)        {            u = i, num ++;        }    memset(used, false, sizeof(used));    rdfs(u, 0);    for(int i=0; i<v; ++ i)        if(used[i] == false)        {            num = 0;            break;        }    printf("%d\n", num);}
View Code

 注:新学的强联通分量,那里不对请指出, 万分感谢!

POJ 2186-Popular Cows (图论-强联通分量Korasaju算法)