题解 P2812 【校园网络】

· · 题解

完全不知道我用的是什么算法，只知道用了图诶（摊手）。

sort大法吼！

楼下@土间埋 大佬的思路已经十分清晰了，明显是 P2835刻录光盘 结果输出两次，数据加强的版本。

在排序中，详细的思路见 刻录光盘的排序思路

    #include<iostream>
    #include<algorithm>
    using namespace std;
    short pic[10002][10002]={0},n,team[10002]={0},s=0;
    //pic为邻接矩阵，team为递归连接顺序
    bool jyh[10002]={0};
    void dg(int k)
    {
        jyh[k]=1;
        for(int i=1;i<=n;i++)
            if(!jyh[i]&&pic[k][i]) dg(i);
    }
    bool ss(int a,int b)
    {
        if(pic[a][0]!=pic[b][0]) return pic[a][0]<pic[b][0];
        else return pic[a][10001]>pic[b][10001];
    }
    int main()
    {
        cin>>n;//输入n所学校
        for(int i=1,q;i<=n;i++)
        {
            team[i]=i;//初始化顺序
            cin>>q;//输入可到达学校
            while(q!=0)
            {
                pic[i][q]=1;
                pic[q][0]++;
                pic[i][10001]++;
                cin>>q;
            }
        }
        sort(team+1,team+1+n,ss);//排序
        for(int i=1;i<=n;i++)
        {
            if(!jyh[team[i]])
            {
                s++;dg(team[i]);//把可连接的学校都连上
            }
        }
        cout<<s<<endl<<s<<endl;//输出两遍
}`