読者です 読者をやめる 読者になる 読者になる

AOJ 0119 Taros Obsession

Graph Algorithms C/C++ AOJ

問題

(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0119)。

解法

なんか論理の問題かな、推論とかするのかなと思っていたら、

(きこえますか...あなたの脳内に...直接語りかけています...トロピカル...いえ...トポロジカルソートを使うのです)

って聞こえたので。 http://www.prefield.com/algorithm/さんを参考にして実装しました。

コード

struct Edge{
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight):
    src(src), dst(dst), weight(weight){}
};

bool operator<(const Edge &e, const Edge &f){
  return e.weight != f.weight ? e.weight > f.weight :
    e.src != f.src ? e.src > f.src : e.dst > f.dst;
}

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

bool visit(const Graph &g, int v, vector<int> &order, vector<int> &color){
  color[v] = 1;
  FOR(e, g[v]){
    if(color[e->dst] == 2) continue;
    if(color[e->dst] == 1) return false;
    if(!visit(g, e->dst, order, color)) return false;
  }
  order.push_back(v); color[v] = 2;
  return true;
}

bool topologicalSort(const Graph &g, vector<int> &order){
  int n = g.size();
  vector<int> color(n);
  rep(u, n) if(!color[u] && !visit(g, u, order, color))
    return false;
  reverse(ALL(order));
  return true;
}


int main(){
  int m, n, x, y;
  scanf("%d%d", &m, &n);
  Graph g(m);

  rep(i, n){
    scanf("%d%d", &x, &y); x--; y--;
    g[x].push_back(Edge(x, y, 1));
  }

  vector<int> res;
  if(topologicalSort(g, res)){
    rep(i, res.size())
      printf("%d\n", res[i]+1);
  }

  return 0;
}