欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Week8—C—班长竞选(强连通子图 SCC)

程序员文章站 2022-07-12 18:15:35
...

题目描述:

大学班级选班长,N 个同学均可以发表意见 若意见为 A B 则表示 A 认为 B 合适,意见具有传递性,即 A 认为 B 合适,B 认为 C 合适,则 A 也认为 C 合适 勤劳的 TT 收集了M条意见,想要知道最高票数,并给出一份候选人名单,即所有得票最多的同学,你能帮帮他吗?


Input:

本题有多组数据。第一行 T 表示数据组数。每组数据开始有两个整数 N 和 M (2 <= n <= 5000, 0 <m <= 30000),接下来有 M 行包含两个整数 A 和 B(A != B) 表示 A 认为 B 合适。

Output:

对于每组数据,第一行输出 “Case x: ”,x 表示数据的编号,从1开始,紧跟着是最高的票数。 接下来一行输出得票最多的同学的编号,用空格隔开,
不忽略行末空格!


个人思路:

强连通分量:

  • 有向图中的概念
  • 强连通:有向图G中任意两个节点连通
  • 强连通分量(SCC):极大的强联通子图

example:

Week8—C—班长竞选(强连通子图 SCC)

  • 蓝线为SCC之间的边
  • 红框框起来的是单个SCC

Kosaraju算法

  • 目标:找到有向图中所有的SCC

  • 算法步骤:

     1、第一遍DFS确定**原图**的逆后序序列;
     2、第二遍DFS在**反图**中按照原图的逆后序序列进行遍历
     3、每次由起点遍历到的点再到起点构成一个SCC
    

反图即是将原图中的所有边反向。

本题解释:

  • 因为求的是每个人得票的总数,暴力一点的话,枚举每个人,然后遍历他所能到达的点。毫无疑问超时。
  • 利用SCC求解。我们用SCC进行缩点,缩点后,对于第i个SCC来说,答案分为两部分,令SCC[i]表示第i个SCC中的个数;
  • 只考虑当前SCC中点,得票数 ans = SCC[i] - 1;
  • 考虑其他SCC,ans = SCC[i] - 1 + SUM( SCC[j] ),其中 j 可达到 i。
  • 用反证法可以证明,得票数最多的一定出现在出度为0的SCC中。

实现细节:

  • 本题涉及到三个图:原图、反图、SCC缩点后的图;对应代码中的G,G1,G2,
  • 在得到G2后,在G2中对每个入度为0的SCC进行DFS,计算它的总的票数。
  • 按字典序输出得票数最多的SCC中的点。

代码块:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 5e3 + 5;
int n, num, m, scnt, dcnt, vis[maxn], dfsn[maxn], c[maxn], outd[maxn], re[maxn], number[maxn], flag[maxn];
// n-点的个数;num-当前待求scc的最长路径;m-边的个数;scnt-scc的个数,dcnt-后序索引;vis-用于后序遍历;dfsn-后序序列;c[i]-i所在的scc
// outd[i]-记录缩点后scc的出度,re[c[i]]-i点所在scc的maxnum,number[c[i]]-i点所在scc的num;flag-用于dfs求结果。
vector<int>G[maxn], G2[maxn], G3[maxn];//G为原图,G2为反图,G3为SCC图
struct node{//b代表SCC中的点,a表示b所在的SCC
    int a,b;
    node(int x, int y){a = x; b = y;}
    bool operator<(const node&t)const {
        return b < t.b;
    }
};
priority_queue<node>op1;//用于字典序输出
void dfs1(int x) {//post index
    vis[x] = 1;
    for (int i = 0; i < G[x].size(); ++i) if (!vis[G[x][i]])dfs1(G[x][i]);
    dfsn[++dcnt] = x;
}
void dfs2(int x) {//inv post index
    c[x] = scnt; number[scnt]++;
    for (int i = 0; i < G2[x].size(); ++i)
        if (!c[G2[x][i]])dfs2(G2[x][i]);
        else if(c[G2[x][i]] != c[x])G3[c[x]].push_back(c[G2[x][i]]), outd[c[G2[x][i]]] = 1;// cout << c[x] <<"," << c[G2[x][i]] <<endl;//Graph three
}
void dfs_result(int x){
    num += number[x];flag[x] = 1;
    for(int i = 0; i < G3[x].size(); ++i)if(!flag[G3[x][i]])dfs_result(G3[x][i]);
}
void kosaraju() {
    dcnt = scnt = 0;
    for (int i = 0; i < n; ++i)if (!vis[i])dfs1(i);
    for (int i = dcnt; i > 0; --i)if (!c[dfsn[i]])++scnt, dfs2(dfsn[i]);
}

int main() {
    int t;
    cin >> t;
    for(int k = 1; k <= t; ++k) {
        cin >> n >> m;
        int max_num = -1;//记录最大得票数
        for (int i = 0; i <= n; ++i)vis[i] = 0, re[i] = 0,c[i] = 0, outd[i] = 0, number[i] = 0, flag[i] = 0, G[i].clear(), G2[i].clear(), G3[i].clear();
        int u, v;
        for (int i = 0; i < m; ++i) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G2[v].push_back(u);
        }
        kosaraju();
        for(int i = 1; i <= scnt; ++i){
            if(!outd[i]){
                num = -1;
                for(int j = 1; j <= scnt; ++j)flag[j] = 0;
                dfs_result(i);
                if(op1.empty())op1.push(node(i,num)), max_num = num;
                else if(num > max_num) {op1.pop(); op1.push(node(i,num)), max_num = num;}
                else if(num == max_num)op1.push(node(i,num));
            }
        }

        while(!op1.empty() && op1.top().b == max_num){re[op1.top().a] = max_num; op1.pop();}
        while(!op1.empty())op1.pop();//clear op1
        //output  Case 1: 2
        cout << "Case " << k << ": " << max_num << endl;
        int x = 0, y = 0, pp[maxn];
        for(; x < n; ++x)if(re[c[x]] == max_num) pp[++y] = x;
        for(int i = 1; i < y; ++i)cout << pp[i] << " ";
        cout << pp[y] <<endl;
    }
    return 0;
}