dmx7u19x @ 2023-08-31 13:57:16
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> a[1200];
vector<int> G[1200];
int r[1200];
int v[1200];
bool m1 [1200][1200];
int main()
{
cin>>n>>m;
map< pair<int,int> ,bool > mp;
for(int i=1;i<=m;i++)
{
int t=0;
cin>>t;
for(int j=0;j<=t-1;j++)
{
int p=0;
cin>>p;
a[i].push_back(p);
m1[i][p]=1;
}
for(int j=0;j<a[i].size();j++)//停靠枚举站点
{
for(int z=a[i][0];z<a[i][a[i].size()-1];z++)//枚举起始站中间的站点
{
if(m1[i][z]==1)
{
continue;
}
pair<int,int> pr;
pr.first=a[i][j];
pr.second=z;
if(mp.count(pr)==0)
{
G[a[i][j]].push_back(z);
r[z]++;
//cout<<i;
mp[pr]=1;
}
else
continue;
}
}
}
queue< pair<int,int> > q;//表示站点和拓扑轮数
for(int i=1;i<=n;i++)
{
if(r[i]==0)
{
pair<int,int> pr;
pr.first=i;
pr.second=1;
q.push(pr);
v[i]=1;
}
}
pair<int,int> u;
int ret=0;
while(!q.empty())//拓扑排序
{
u=q.front();
//cout<<u.first<<" ";
q.pop();
for(int i=0;i<G[u.first].size();i++)
{
r[G[u.first][i]]--;
if(r[G[u.first][i]]==0&&v[G[u.first][i]]==0)
{
pair<int,int> pr;
pr.first=G[u.first][i];
pr.second=u.second+1;
ret=max(ret,pr.second);
q.push(pr);
v[pr.first]=1;
}
}
}
cout<<ret;
return 0;
}
by lucky_baizq @ 2023-08-31 14:11:52
你的时间复杂度