Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Sort Items by Groups Respecting Dependencies

Problem (yeniden ifade)

n öğe, bazıları gruplarda (group[i] veya -1 serbest). beforeItems[i] önkoşulları listeler. Grup üyeleri bitişik ve önkoşullar sağlanmış geçerli bir sıra döndür; imkânsızsa boş.

Sezgi

Serbest öğelere benzersiz gruplar ata. Gruplar arası kenarlarla grupları topo-sort et; göreli sıra için öğeleri topo-sort et; her grubun üyelerini küresel öğe sırasıyla yaz.

Yaklaşımlar

Çift topological sort (gruplar + öğeler)

Doğrulanmadı

Zaman O(n + e)Alan O(n + e)

Fikir. İki graf: öğe düzeyi ve grup düzeyi. Birinde döngü → []. Son indeksleri beforeItems’a karşı doğrula.

Yürüyüş. İki grup ve çapraz kenarlı küçük n, önce grup blok sırasını sonra içindeki öğeleri zorlar.

Trade-off. Bitişiklik, grup topo sırasından tüm grup bloklarını yazarak sağlanır.

Çözüm

export function sortItems(
  n: number,
  m: number,
  group: number[],
  beforeItems: number[][],
): number[] {
  group = [...group];
  let gid = m;
  for (let i = 0; i < n; i++) if (group[i] === -1) group[i] = gid++;
  const gCount = gid;
  const itemG: number[][] = Array.from({ length: n }, () => []);
  const itemIndeg = Array(n).fill(0);
  const groupEdgeSet = new Set<string>();
  for (let v = 0; v < n; v++) {
    for (const u of beforeItems[v]!) {
      itemG[u]!.push(v);
      itemIndeg[v]!++;
      if (group[u] !== group[v]) groupEdgeSet.add(`${group[u]},${group[v]}`);
    }
  }
  const groupG: number[][] = Array.from({ length: gCount }, () => []);
  const groupIndeg = Array(gCount).fill(0);
  for (const key of groupEdgeSet) {
    const [a, b] = key.split(",").map(Number) as [number, number];
    groupG[a]!.push(b);
    groupIndeg[b]!++;
  }
  const kahn = (graph: number[][], indeg: number[], nodes: number[]): number[] | null => {
    const local = [...indeg];
    const set = new Set(nodes);
    const q = nodes.filter((u) => local[u] === 0);
    const order: number[] = [];
    while (q.length) {
      const u = q.shift()!;
      order.push(u);
      for (const v of graph[u]!) {
        if (!set.has(v)) continue;
        if (--local[v]! === 0) q.push(v);
      }
    }
    return order.length === nodes.length ? order : null;
  };
  const groupOrder = kahn(groupG, groupIndeg, [...Array(gCount).keys()]);
  if (!groupOrder) return [];
  const itemOrder = kahn(itemG, itemIndeg, [...Array(n).keys()]);
  if (!itemOrder) return [];
  const pos = new Map(itemOrder.map((x, i) => [x, i]));
  const members: number[][] = Array.from({ length: gCount }, () => []);
  for (let i = 0; i < n; i++) members[group[i]!]!.push(i);
  const res: number[] = [];
  for (const gr of groupOrder) {
    const mem = [...members[gr]!].sort((a, b) => pos.get(a)! - pos.get(b)!);
    res.push(...mem);
  }
  const idx = new Map(res.map((x, i) => [x, i]));
  for (let v = 0; v < n; v++) {
    for (const u of beforeItems[v]!) {
      if (idx.get(u)! >= idx.get(v)!) return [];
    }
  }
  return res;
}

export function sortItems(
  n: number,
  m: number,
  group: number[],
  beforeItems: number[][],
): number[] {
  group = [...group];
  let gid = m;
  for (let i = 0; i < n; i++) if (group[i] === -1) group[i] = gid++;
  const gCount = gid;
  const itemG: number[][] = Array.from({ length: n }, () => []);
  const itemIndeg = Array(n).fill(0);
  const groupEdgeSet = new Set<string>();
  for (let v = 0; v < n; v++) {
    for (const u of beforeItems[v]!) {
      itemG[u]!.push(v);
      itemIndeg[v]!++;
      if (group[u] !== group[v]) groupEdgeSet.add(`${group[u]},${group[v]}`);
    }
  }
  const groupG: number[][] = Array.from({ length: gCount }, () => []);
  const groupIndeg = Array(gCount).fill(0);
  for (const key of groupEdgeSet) {
    const [a, b] = key.split(",").map(Number) as [number, number];
    groupG[a]!.push(b);
    groupIndeg[b]!++;
  }
  const kahn = (graph: number[][], indeg: number[], nodes: number[]): number[] | null => {
    const local = [...indeg];
    const set = new Set(nodes);
    const q = nodes.filter((u) => local[u] === 0);
    const order: number[] = [];
    while (q.length) {
      const u = q.shift()!;
      order.push(u);
      for (const v of graph[u]!) {
        if (!set.has(v)) continue;
        if (--local[v]! === 0) q.push(v);
      }
    }
    return order.length === nodes.length ? order : null;
  };
  const groupOrder = kahn(groupG, groupIndeg, [...Array(gCount).keys()]);
  if (!groupOrder) return [];
  const itemOrder = kahn(itemG, itemIndeg, [...Array(n).keys()]);
  if (!itemOrder) return [];
  const pos = new Map(itemOrder.map((x, i) => [x, i]));
  const members: number[][] = Array.from({ length: gCount }, () => []);
  for (let i = 0; i < n; i++) members[group[i]!]!.push(i);
  const res: number[] = [];
  for (const gr of groupOrder) {
    const mem = [...members[gr]!].sort((a, b) => pos.get(a)! - pos.get(b)!);
    res.push(...mem);
  }
  const idx = new Map(res.map((x, i) => [x, i]));
  for (let v = 0; v < n; v++) {
    for (const u of beforeItems[v]!) {
      if (idx.get(u)! >= idx.get(v)!) return [];
    }
  }
  return res;
}

Şablon bağlantısı

İki hiyerarşi düzeyinde topological sort.

Yansıma

İki sıralama: gruplar arası ve grup içi. Madde bağı farklı gruptaysa grup kenarı da olur. Grup −1 kendi başına bir gruptur.
Döngü grupta veya maddede: boş liste. Önce grup sırası, her grupta madde sırası.
Bağımlılık yok: herhangi sıra geçerli. Hepsi −1 ise tek grup içinde Kahn.