[强连通分量]分组

希望更好的阅读体验？点这里

题目

描述

信息学竞赛班的班主任Smart是一位心思很缜密的老师，他在接手信息学竞赛班一个学期以后，想调查一下班上同学之间相互交流的情况，以便及时了解班级动态。
信息学竞赛班一共有 n n n 个同学。这 n n n 位同学每一个人都有一个小花名册，名册里面写着他所愿意交流的人的名字。比如说在 A A A 的人名单里写了 B B B ，那么表示 A A A 愿意与 B B B 交流；但是 B B B 的名单里不见得有 A A A ，也就是说 B B B 不见得想与 A A A 交流。但是如果 A A A 愿意与 B B B 交流， B B B 愿意与 C C C 交流，那么 A A A 一定愿意与 C C C 交流。也就是说交流有传递性。
班主任Smart觉得需要将这 n n n 个人分为 m m m 组，要求每一组的任何一人都愿意与组内其他人交流。并求出一种方案以确定 m m m 的最小值是多少。

输入

第一行一个整数 n n n（ 1 ≤ n ≤ 200 1 \le n \le 200 1≤n≤200）。
接下来 n n n 行，第 ( i + 1 ) (i+1) (i+1) 行表示编号为 i i i 的人的小花名册名单，名单以 0 0 0 结束。
注意：自己的名单里面不会有自己的名字。

输出

一行，一个整数 m m m 。

输入样例

5
2 0
1 0
4 5 0
3 0
4 0

输出样例

2

样例解释

样例中 1 1 1 和 2 2 2 分在一组， 3 3 3 、 4 4 4 和 5 5 5 分在一组。

分析

分成的每组都要求任何人都愿意与组内其他人交流，指的就是对于每组中任意两个顶点 u u u 和 v v v ，从 u u u 到 v v v 有一条路径，同时从 v v v 到 u u u 又有一条路径。又因为分组数最小，所以求强连通分量的个数就行了，下面提供两种方法：

1.Tarjan

不会Tarjan的戳这里

如果知道题目求的是强连通分量的话，这道题就是Tarjan模板题，注意读入。

#include <cstdio>
#include <stack>
#define min(a,b) ((a)<(b)?(a):(b))
struct Edge{
    int to,next;
}e[40003];
int n,head[203],len,ans,dfn[203],low[203],index;
std::stack<int> s;
bool ins[203];//ins表示是否在栈内
void add(int &u,int &v){
    e[++len].next=head[u],head[u]=len,e[len].to=v;
}
void tarjan(int x){
    dfn[x]=low[x]=++index;
    s.push(x);
    ins[x]=1;
    for(int i=head[x];i;i=e[i].next){
        if(!dfn[e[i].to])
            tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);
        else if(ins[e[i].to])
            low[x]=min(low[x],dfn[e[i].to]);
    }
    if(dfn[x]==low[x]){
        int cnt=0;
        while(1){
            int u=s.top();
            s.pop();
            ins[u]=0;
            ++cnt;
            if(x==u){
                ans++;
                break;
            }
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        while(1){
            scanf("%d",&x);
            if(!x) break;
            add(i,x);
        }
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    printf("%d\n",ans);
    return 0;
}

2.Floyd

如果不会写Tarjan，可以用Floyd解决。

设 f [ i ] [ j ] f[i][j] f[i][j] 表示 i i i 是否愿意与 j j j 交流，则 KaTeX parse error: Expected 'EOF', got '&' at position 16: f[i][j]=f[i][k]&̲&f[k][j] 。

再设 v i s [ i ] vis[i] vis[i] 表示第 i i i 个人是否被分过组，枚举每一个 i i i ，如果 i i i 没分过组，枚举 j = i + 1 … n j=i+1 \dotsc n j=i+1…n ，如果 f [ i ] [ j ] f[i][j] f[i][j] 和 f [ j ] [ i ] f[j][i] f[j][i] 同时为真，说明有一个强连通分量，让 v i s [ j ] = 1 vis[j]=1 vis[j]=1 ，具体代码如下：

#include <cstdio>
bool f[203][203],vis[203];
void floyd(int &n){
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j&&j!=k&&k!=i) f[i][j]=f[i][j]||f[i][k]&&f[k][j];//因为没有单独用一个邻接矩阵，所以要写成这样
}
int main(){
    int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;
        while(1){
            scanf("%d",&x);
            if(!x) break;
            f[i][x]=1;
        }
    }
    floyd(n);
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            ++ans;//ans在这里加1
            for(int j=i+1;j<=n;j++) if(f[i][j]&&f[j][i]) vis[j]=1;
        }
    }
    printf("%d\n",ans);
    return 0;
}