Cod sursa(job #1244193)

Utilizator danny794Dan Danaila danny794 Data 16 octombrie 2014 21:24:11
Problema Arbori de intervale Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>
#include <vector>
#include <queue>

#define NMAX 50005

using namespace std;

int N, M;
int count[NMAX];
vector<int> edges[NMAX];
queue<int> freeNodes;

void read()
{
  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w", stdout);
  scanf("%d%d", &N, &M);
  int x, y;
  for(int i = 0; i < M; i++)
  {
    scanf("%d%d", &x, &y);
    edges[x].push_back(y);
    count[y]++;
  }

  for(int i = 1; i <= N; i++)
    if(!count[i])
      freeNodes.push(i);
}

void solve()
{
  while(freeNodes.size())
  {
    int v = freeNodes.front();
    freeNodes.pop();
    printf("%d ", v);
    for(unsigned int i = 0; i < edges[v].size(); i++)
    {
      count[edges[v][i]]--;
      if(!count[edges[v][i]])
        freeNodes.push(edges[v][i]);
    }
  }
}

int main() {
  read();
  solve();
	return 0;
}