萌新刚学OI,求助连样例都没过的拓扑排序

P1983 [NOIP2013 普及组] 车站分级

SIXIANG32 @ 2020-08-03 21:55:18

RT

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
vector<int>gra[100100];
int d[100100];
int a[100100];
int level[100100];
bool vis[100100];
bool vv[1010][1010];
int n,m,k,ans=0;
void link(int x,int y)
{
    gra[x].push_back(y);
    d[y]++;
}
int dfs()
{
    int tot=0;
    queue<int>que;
    for(int p=1;p<=n;p++)
        if(!d[p])
            que.push(p),level[p]=1;
    while(!que.empty())
    {
        int fr=que.front();
        que.pop();
        tot++;
        for(int p=0;p<gra[fr].size();p++)
        {
            d[gra[fr][p]]--;
            if(!d[gra[fr][p]])
            {
                level[gra[fr][p]]=level[fr]+1;
                ans=max(ans,level[gra[fr][p]]);
                que.push(gra[fr][p]);
            }
        }
    }
    return ans;
}
signed main()
{
    int s;
    cin>>n>>m;
    for(int p=1;p<=m;p++)
    {
        cin>>s;
        for(int i=1;i<=s;i++)
            cin>>a[i];
        for(int i=1;i<=si++)
            for(int j=i+1;j<=s;j++)
                if(!vv[a[i]][a[j]])
                {
                    vv[a[i]][a[j]]=1;
                    link(a[i],a[j]);    
                }
    }
    cout<<dfs()<<endl;
    for(int i=1;i<=n;i++)
        cout<<level[i]<<" ";
    return 0;
}

求助啊,调不动了/kk


by SIXIANG32 @ 2020-08-03 22:12:39

额,好像复制粘贴时手抖了(大雾
能帮我康康拓扑里面吗?


by VioletIsMyLove @ 2020-08-03 22:15:16

不太看得懂。。。还要弄懂您是怎么存的图。。。变量名奇特,码风奇特,理解中。


by VioletIsMyLove @ 2020-08-03 22:17:36

毕竟方法不同。。。


by SIXIANG32 @ 2020-08-03 22:20:18

@amhxyp az
vector存图和链表前向星不是差不多嘛/yiw


by VioletIsMyLove @ 2020-08-03 22:21:26

也就是变表咯?


by VioletIsMyLove @ 2020-08-03 22:21:37

边表


by SIXIANG32 @ 2020-08-03 22:22:38

@amhxyp ?
边表是啥?/yiw
蒟蒻tcl,没听说过/kk


by VioletIsMyLove @ 2020-08-03 22:22:57

人眼过了2趟感觉没啥大问题。。。(雾

可能是我太弱了吧


by VioletIsMyLove @ 2020-08-03 22:23:50

@SIXIANG 不是3种存图方式,邻节矩阵,边表,邻节表吗


by VioletIsMyLove @ 2020-08-03 22:24:16

给你看看我代码


上一页 | 下一页