KGW_源 @ 2019-07-16 19:27:39
RT,下载下数据感觉应该是读入问题,但实在不知道具体怎么改
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
#define INF 0x3f3f3f
#define maxn 10010
#define clear(a) memset(a,0,sizeof a)
int n, m, tot, ans, num1, num2;
int first[maxn], in[maxn], vis[maxn][maxn], lazy[maxn];
struct node{
int num, z[maxn>>1];
} f[maxn>>1];
struct edge{
int nextx, to;
} e[maxn];
queue<int> Q;
void add(int u,int v)
{
tot++;
e[tot].nextx = first[u];
first[u] = tot;
e[tot].to = v;
in[v]++;
}
void solve(int id,int x)
{
int lazy = 0;
for (int i = 1; i <= f[id].num;i++)
if(x==f[id].z[i])
{
lazy = 1;
break;
}
if(lazy==1)
return;
else
{
for (int i = 1; i <= f[id].num;i++)
if(!vis[x][f[id].z[i]])
add(x, f[id].z[i]), vis[x][f[id].z[i]] = 1;
}
}
void tuopu()
{
for (int i = 1; i <= n;i++)
if(!in[i])
Q.push(i), num1++;
while(!Q.empty())
{
if(!num1)
ans++, num1 = num2, num2 = 0;
num1--;
int u = Q.front();
Q.pop();
for (int i = first[u]; i;i=e[i].nextx)
{
int v = e[i].to;
in[v]--;
if(in[v]==0)
Q.push(v), num2++;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m;i++)
{
scanf("%d", &f[i].num);
clear(lazy);
for (int j = 1; j <= f[i].num;j++)
{
scanf("%d", &f[i].z[j]);
lazy[f[i].z[j]] = 1;
}
for (int j = f[i].z[1]; j <= f[i].z[f[i].num]; j++)
{
if(lazy[j])
continue;
solve(i, j);
}
}
tuopu();
cout << ans + 1;
return 0;
}