题解 P2812 【校园网络】

zhylj · 2018-01-04 16:00:24 · 题解

这种数据还是比较水的…

（是同机房dalao的思路！！！

事实上，有几个强连通分量，就需要添加几个边，才能连通

所以只要输出两遍结果就可以了。。。

Kosaraju算法（效率较低：

    #include<cstdio>
    using namespace std;
    bool pic[10005][10005]={0},po[10005]={0}; //pic存邻接矩阵
    int n,a,h=0,sum=0;
    inline void dfs(const int &i)
    {
        po[i]=1; //设置这个店已经遍历过了
        for(register int j=1;j<=n;j++)  //遍历所有点
            if(!po[j]&&pic[i][j])  //如果可以走并没有走过，遍历
                dfs(j);  //遍历，进入递归
    }
    int main()
    {
        scanf("%d",&n); //输入
        for(register int i=1;i<=n;i++)
            do
            {
                scanf("%d",&a);  //输入
                pic[i][a]=1;  //设置邻接矩阵
            }
            while(a!=0);  //如果输入到0停止
        for(register int i=1;i<=n;i++)
            if(sum+=!po[i])  //如果这个店没被遍历过，就开始遍历
                dfs(i);  //遍历
        printf("%d\n%d\n",sum,sum);  //输出解
        return 0;
}