O código original, que utiliza uma abordagem de O(n²) para construir o grafo, resultou em um tempo de execução de 772ms. A principal causa dessa complexidade é a maneira como as arestas são adicionadas entre os nós.

#include<bits>
#define int long long
using namespace std;
const int N=1e6+10,M=1e4+10;
int n,m,res,f[N],p[N],a[N],s,k,level[N];
int e[N],ne[N],h[N],idx;
bool vis[N],mp[M][M];
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void topsort()
{
    queue<int>que;
    for(int i=1;i<=n;i++) if(!p[i]) que.push(i);
    while(!que.empty()){
        int now=que.front(); que.pop();
        for(int i=h[now];~i;i=ne[i]){
            int j=e[i];
            p[j]--;
            if(p[j]==0) level[j]=level[now]+1,que.push(j);
        }
    }
}

void spfa()
{
    queue<int>que;
    que.push(0),level[0]=0,vis[0]=true;
    while(!que.empty()){
        int now=que.front(); que.pop();
        vis[now]=false;
        for(int i=h[now];~i;i=ne[i]){
            int j=e[i];
            if(level[j]<level cin="" dfs="" for="" i="h[u];~i=ne[i])" if="" int="" level="" main="" return="" signed="" std::ios::sync_with_stdio="" u="" vis="">>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m cin="">>k;
        memset(vis,false,sizeof vis);
        for(int j=0;j<k cin="">>a[j],vis[a[j]]=true;
        for(int j=a[0];j<=a[k-1];j++){
            if(vis[j]) continue;
            for(int e=0;e<k cout="" for="" i="1;i<=n;i++)" if="" memset="" mp="" res="max(res,dfs(i));" return="" vis=""></k></k></m></level></int></int></bits>

Otimização com Ponto Virtual

Uma otimização significativa pode ser alcançada ao introduzir um ponto virtual. Em vez de conectar diretamente todos os elementos de um conjunto a todos os elementos fora dele (o que leva a O(n²) arestas em casos extremos), podemos adicionar um ponto virtual intermediário. Isso reduz a complexidade da adição de arestas para O(n) por conjunto, resultando em um total de O(nm) arestas e melhorando drasticamente o tempo de execução.

Com essa abordagem, o tempo de execução foi reduzido para 244ms, com o uso de apenas 13.34MB de memória e 0.69KB de código.

A lógica principal é a seguinte:

• Para cada conjunto de elementos fornecido, criamos um ponto virtual (n + i, onde i é o índice do conjunto).
• Adicionamos arestas do ponto virtual para cada eelmento dentro do conjunto.
• Adicionamos arestas de cada elemento fora do conjunto para o ponto virtual correspondante.
• A função DFS, ao calcular o nível de um nó, agora considera a subtração de 1 se o nó for um ponto virtual, garnatindo que apenas os nós originais contribuam para o comprimento do caminho.

#include<bits>
#define int long long
using namespace std;
const int N=1e6+10,M=1e4+10;
int n,m,res,f[N],p[N],a[N],s,k,level[N];
int e[N],ne[N],h[N],idx;
bool vis[N],mp[M][M]; // mp não é mais usado na versão otimizada
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

// topsort e spfa não são diretamente usados na solução final, mas são mantidos para referência
void topsort()
{
    queue<int>que;
    for(int i=1;i<=n;i++) if(!p[i]) que.push(i);
    while(!que.empty()){
        int now=que.front(); que.pop();
        for(int i=h[now];~i;i=ne[i]){
            int j=e[i];
            p[j]--;
            if(p[j]==0) level[j]=level[now]+1,que.push(j);
        }
    }
}

void spfa()
{
    queue<int>que;
    que.push(0),level[0]=0,vis[0]=true;
    while(!que.empty()){
        int now=que.front(); que.pop();
        vis[now]=false;
        for(int i=h[now];~i;i=ne[i]){
            int j=e[i];
            if(level[j]<level calculado="" dfs="" foi="" for="" i="h[u];~i;i=ne[i])" if="" int="" j="" level="" max_level="0;" memorizado="" o="" ponto="" retorna="" return="" se="" u="" um="" valor="" virtual="" vis=""> n), não contamos ele como um nível real no caminho final.
    // A subtraçao é feita aqui caso o nó virtual nao tenha saido do loop
    if(u > n) level[u]--;
    return level[u];
}
signed main()
{
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++){ // Loop pelos 'm' conjuntos
        cin>>k;
        memset(vis,false,sizeof vis);
        for(int j=1;j<=k;j++) cin>>a[j],vis[a[j]]=true,add(n+i,a[j]); // Adiciona arestas do ponto virtual (n+i) para cada elemento no conjunto
        for(int j=a[1];j<=a[k];j++){ // Itera sobre o intervalo dos elementos do conjunto
            if(vis[j]) continue; // Pula se o elemento já faz parte do conjunto atual
            add(j,n+i); // Adiciona aresta do elemento para o ponto virtual (n+i)
        }
    }

    // O cálculo do resultado final é feito através da DFS a partir dos nós que não têm dependências de entrada (nível 0 implícito)
    for(int i=1;i<=n;i++) {
        // Verificamos se o nível já foi calculado (pode acontecer se for alcançado por outro nó)
        if(!level[i]) {
            res=max(res,dfs(i));
        }
    }
    cout<<res ajuste="" ap="" considera="" corretos="" da="" dfs="" j="" n="" o="" os="" para="" pontos="" resultado="" return="" virtuais=""></res></level></int></int></bits>