HPU 3639--Hawk-and-Chicken【SCC缩点反向建图 && 求传递的最大值】

Hawk-and-Chicken

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2409    Accepted Submission(s): 712

Problem Description

Kids in kindergarten enjoy playing a game called Hawk-and-Chicken. But there always exists a big problem: every kid in this game want to play the role of Hawk.
So the teacher came up with an idea: Vote. Every child have some nice handkerchiefs, and if he/she think someone is suitable for the role of Hawk, he/she gives a handkerchief to this kid, which means this kid who is given the handkerchief win the support. Note the support can be transmitted. Kids who get the most supports win in the vote and able to play the role of Hawk.(A note:if A can win
support from B(A != B) A can win only one support from B in any case the number of the supports transmitted from B to A are many. And A can't win the support from himself in any case.
If two or more kids own the same number of support from others, we treat all of them as winner.
Here's a sample: 3 kids A, B and C, A gives a handkerchief to B, B gives a handkerchief to C, so C wins 2 supports and he is choosen to be the Hawk.

 

Input

There are several test cases. First is a integer T(T <= 50), means the number of test cases.
Each test case start with two integer n, m in a line (2 <= n <= 5000, 0 <m <= 30000). n means there are n children(numbered from 0 to n - 1). Each of the following m lines contains two integers A and B(A != B) denoting that the child numbered A give a handkerchief to B.

 

Output

For each test case, the output should first contain one line with "Case x:", here x means the case number start from 1. Followed by one number which is the totalsupports the winner(s) get.
Then follow a line contain all the Hawks' number. The numbers must be listed in increasing order and separated by single spaces.

 

Sample Input

2
4 3
3 2
2 0
2 1

3 3
1 0
2 1
0 2

 

Sample Output

Case 1: 2
0 1
Case 2: 2
0 1 2

 

题意：如今有n个孩子正在玩游戏，完毕一个传递的游戏，举个样例，A传递到B小朋友，然后B小朋友传递给C小朋友。那么此时，C小朋友将拥有2的传递值，C是胜利者，若C又传递回A。那么A,B,C三者都拥有传递值为2的胜利者。问胜利着获得的最大传递值，以及胜利者的编号（可能有多个）。

解析：这题的 n的数据量为5000， 暴力肯定是不行的，有题意可知：如有 A - > B,  B - > C, C - >A。那么A。B，C都是拥有传递值为2的胜利者。

所以我们能够先缩点求出SCC。对每一个SCC内的点来说。 它们的传递值是一样的，但要明确：假设从一个SCC：a， 传到还有一个SCC：b， 即 a - > b。传递的值为SCC a 内部点的个数。这点要清楚

并且我们知道，胜利者肯定在那些出度为0的SCC中，所以我们能够从每一个入度为0的SCC開始搜索，DFS遍历一遍，得到每一个出度为0的SCC的传递值，找出最大的就可以，

但这样的思路是不正确的，由于入度为0的SCC的个数肯定远远的大于出度为0的SCC个数，并且这题的n是很大的。枚举每一个入度为0的SCC然后DFS遍历一遍肯定会超时。

所以我们要反向建图， 这样每次从入度为0的SCC【即正向建边出度为0 的SCC】開始DFS，就能够得到每一个入度为0的SCC的传递值。

找出当中传递值最大的。这里还有注意

当我们找这个传递值最大的SCC ：A 时，我们把这SCC的传递值多算了1，由于我们算的时候是累加的每一个SCC中点的个数。

当找到传递值最大的SCC A时，它内部的传递值为  内部点的个数 - 1。（如A - > B,  B - > C, C - >A，传递值为2），但我们加的时候没有 - 1，所以最后的结果 - 1才是正确答案，这点比較绕，我解释的也不是太清楚。读者自己多想想。不是太难明确。

明天開始刷独立集，2-SAT。 强连通就先做到这。。

这应该是有史以来自己写的最长的解析了，曾经直接总是懒得写题解。认为能写出AC代码即可了，有时懒省事就粘一下别人的。但如今才发现自己写解析的时候收获才最大的，曾经真真真真真蠢。能把自己的思路完整的用文字呈现出来。肯定是比較理解解题的思路了。以后解析都要自己写。还要好好写。加油阿欢。

<pre name="code" class="cpp">#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define maxn 5000 + 500
#define maxm 30000 + 3000
using namespace std;

struct node{
    int u, v, next;
};

node edge[maxm];

int head[maxn], cnt;
int low[maxn], dfn[maxn];
int dfs_clock;
int Belong[maxn];
int scc_clock;
bool Instack[maxn];
int Stack[maxn], top;
bool vis[maxn];//记录缩点后的SCC是否訪问
int in[maxn];//记录SCC的入度
int num[maxn];//记录每一个SCC能得到的最大手帕数
vector<int>scc[maxn];//存储每一个SCC中的节点
vector<int> Map[maxn];//存储缩点后新图
int n, m, k;

void init(){
    cnt = 0;
    memset(head, -1, sizeof(head));
}

void add(int u, int v){
    edge[cnt] = {u, v, head[u]};
    head[u] = cnt++;
}

void getmap(){
    scanf("%d%d", &n, &m);
    int a, b;
    while(m--){
        scanf("%d%d", &a, &b);
        a++, b++;
        add(a, b);
    }
}

void tarjan(int u){
    int v;
    low[u] = dfn[u] = ++dfs_clock;
    Stack[top++] = u;
    Instack[u] = true;
    for(int i = head[u]; i != -1; i = edge[i].next){
        v = edge[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(Instack[v])
            low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u]){
        scc_clock++;
        scc[scc_clock].clear();
        do{
            v = Stack[--top];
            Instack[v] = false;
            Belong[v] = scc_clock;
            scc[scc_clock].push_back(v);
        }while(u != v);
    }
}

void find(){
    memset(low, 0, sizeof(low));
    memset(dfn, 0, sizeof(dfn));
    memset(Belong, 0, sizeof(Belong));
    memset(Stack, 0, sizeof(Stack));
    memset(Instack, false, sizeof(Instack));
    dfs_clock = scc_clock = top = 0;
    for(int i = 1; i <= n; ++i)
        if(!dfn[i]) tarjan(i);
}

void suodian(){//缩点新建图
    for(int i = 1; i <= scc_clock; ++i){
        Map[i].clear();
        in[i] = 0;
    }
    for(int i = 0; i < cnt; ++i){
        int u = Belong[edge[i].u];
        int v = Belong[edge[i].v];
        if(u != v){
            Map[v].push_back(u);//反向建边
            in[u]++;
        }
    }
}

int ans;
void DFS(int u){
    vis[u] = true;
    ans += scc[u].size();
    for(int i = 0; i < Map[u].size(); ++i){
        int v = Map[u][i];
        if(!vis[v]){
            DFS(v);
        }
    }
}

void solve(){
    int sum = -1;
    for(int i = 1; i <= scc_clock; ++i){
        num[i] = 0;
        if(in[i] == 0){
            memset(vis, false, sizeof(vis));
            ans = 0;
            DFS(i);
            num[i] = ans;
            sum = max(num[i], sum);
        }
    }
    printf("Case %d: %d
", k++, sum - 1);//多算1，要减去1
    int flag = 0;
    for(int i = 1; i <= n; ++i){
        if(num[Belong[i]] == sum){
            if(!flag) printf("%d", i - 1);
            else printf(" %d", i - 1);
            flag = 1;
        }
    }
    printf("
");
}

int main(){
    int T;
    scanf("%d", &T);
    k = 1;
    while(T--){
        init();
        getmap();
        find();
        suodian();
        solve();
    }
    return 0;
}