Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

SPOJBRESCALO 11

O problema se trata de saber primeiramente se o grafo de tarefas é acíclico. Se houver um ciclo sabemos que as tarefas não podem ser organizadas em qualquer ordem.

Após verificar que não há ciclos devemos organizar as tarefas de maneira ótima. Em um vetor nós guardamos a qdte de dependências de cada vertice do grafo. No início passamos pela lista de adjacência e todas as tarefas que não tem dependência adicionamos ao heap de mínimo. A cada iteração retiramos o mínimo do heap que será o elemento do topo e reduzimos a dependência do veŕtice do grafo que dependia dessa tarefa. Se o vértice ficar com dependência igual a zero quer dizer que podemos colocá-lo no heap. Fazemos isso até o heap ficar vazio.

Complexidade: n*log(n).


#include<stdio.h>
#include<stdlib.h>
#include<queue>
#define white 1
#define gray 2
#define black 3
#define true 1
#define false 0

std::priority_queue<int> heap;
std::vector<int> vbw;

/* vertice da lista de adjacencia forward */
typedef struct adj_fw{
  int vertex;
  struct adj_fw *next;
}adj_fw;


/* vertice do grafo */
typedef struct node{
  adj_fw *vfw;
  int vbw;
  int color;
}node;

node graph[50000];

void initialize_graph(int size){
  for(int i = 0; i < size; i++){
    graph[i].vfw = NULL;
    graph[i].vbw = 0;
  }
}


void insert_graph(int i, int j){
  adj_fw *newnodefw;
  newnodefw = (adj_fw*) malloc(sizeof(adj_fw));

  newnodefw->vertex = j;
  newnodefw->next = graph[i].vfw;
  graph[i].vfw = newnodefw;

  graph[j].vbw++;
}

void dfs_visit(int u, int size, int *cycle){
  adj_fw *p;

  graph[u].color = gray;

  p = graph[u].vfw;
  while(p){
    if(graph[p->vertex].color == white)
      dfs_visit(p->vertex, size, cycle);
    else if(graph[p->vertex].color == gray)
      *cycle = true;
    p = p->next;
  }

  graph[u].color = black;
}


void dfs(int size, int *cycle){
  *cycle = false;

  for(int i = 0; i < size; i++)
    graph[i].color = white;

  for(int i = 0; i < size; i++)
    if(graph[i].color == white)
      dfs_visit(i, size, cycle);

}


void realize_optimum_line(int size){

  for(int i = 0; i < size; i++)
    if(graph[i].vbw == 0)
      heap.push(-i);


  while(!heap.empty()){
    int op = -heap.top();
    heap.pop();
    printf("%d\n", op);

    adj_fw *p = graph[op].vfw;
    while(p){

      graph[p->vertex].vbw--;

      if(graph[p->vertex].vbw == 0)
        heap.push(-p->vertex);

      p = p->next;
    }
  }

}




void print_graph(int size){
  adj_fw *p;
  printf("Forward:\n");
  for(int i = 0; i < size; i++){
    printf("[%d] ", i);
    p = graph[i].vfw;
    while(p){
      printf("%d -> ", p->vertex);
      p = p->next;
    }
    printf("\n");
  }

}


int main(){
  int n, m, i, j;
  int cycle;

  scanf("%d %d", &n, &m);

  initialize_graph(n);

  while(m--){
    scanf("%d %d", &i, &j);
    insert_graph(i, j);
  }

  dfs(n, &cycle);
  if(cycle)
    printf("*\n");
  else
    realize_optimum_line(n);  


  return 0;
}