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 21:55:53
后面那个输出是调试用的
感觉是连边连错了qwq
by SIXIANG32 @ 2020-08-03 21:57:52
在线等,急!
by int19260817 @ 2020-08-03 22:03:22
@SIXIANG dfs里不用队列啊,直接递归就可以了
by VioletIsMyLove @ 2020-08-03 22:06:36
能说这拓扑看不懂吗。。。
by SIXIANG32 @ 2020-08-03 22:07:07
@axnAyY 啊手残,打的是bfs,函数名写错了
by VioletIsMyLove @ 2020-08-03 22:07:34
仔细一看,车站分级,我去,强悍如斯
by SIXIANG32 @ 2020-08-03 22:08:12
@amhxyp 函数名写错了………………
by VioletIsMyLove @ 2020-08-03 22:10:32
本来说的就不是函数,只是单纯的看不懂,毕竟我太蒟了
by qiuzhehan @ 2020-08-03 22:10:52
for(int i=1;i<=si++)少了;
by VioletIsMyLove @ 2020-08-03 22:11:39
少个;编译怎么过的。。。