aoj 0519 - Worst Reporter

問題

問題概要

試合結果が渡されて、順位がどのように決まるかを求める問題。

解法

まず、試合結果がわからないものは無視して、与えられた試合結果のみを使い、トポロジカルソートをする。aチームが勝ち、bチームが負けた場合、b -> aのような形で辺を貼ることにした。トポロジカルソートをすることで、おおよその順位がわかる。ここからがわからなかった。試合結果がわからなかい所があり、試合結果の順位が一意に決まるのかどうかを判定することができなかった。今回の場合必ず全てのチームの順位が異なるため、クエリのみで形成されたトポロジカルソートの順番が一意に決まっているかどうかを判定すれば良いということになる? ということは、トポロジカルソートしたものの、隣どおしを見て、勝敗が決められているかだけを見れば良いことになる?
下の図はサンプルの時。上の図は隣どおしの頂点において、辺が貼られているので、トポロジカルソートをしたものが一意に決まっている。しかし、下の図が、1と3に辺がはられていないので、1と3を入れ替えた図も書けるので、順序が位置に決まらず、他の順位表も存在するということになる。

図

ミス

トポロジカルソートかな?とは思ったけど、?の部分の処理がわからなかった。ただトポロジカルソートが一意に決まるかを調べるだけ?

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int n;//サッカーチームの数
int m;//与えられた支配の勝敗の個数
vector<int> G[5010];
bool flag[5010];
list <int> out;
void dfs(int u){
    flag[u] = true;
    for(auto v : G[u]){
        if(!flag[v]) dfs(v);
    }
    //トポロジカルソートの先頭から見つかるので、順に先頭に追加していく
    out.push_front(u);
}

int main(void){
    cin >> n;//サッカーチームの数
    cin >> m;//与えられた支配の勝敗の個数
    rep(i, m){
        int a, b; cin >> a >> b;//a勝　b負
        a--; b--;//
        G[b].push_back(a);// b -> a
    }

    rep(i, n){
        if(!flag[i]) dfs(i);
    }

    //出力
    vector<int> memo;
    for(auto itr = out.begin(); itr != out.end(); ++itr){
        memo.push_back(*itr);
    }
    for (int i = memo.size() - 1; i >= 0; --i){
        cout << memo[i] + 1 << endl;//1originになおして出力
    }

    for(int i; i < memo.size() - 1; i++){
        int a = memo[i], b = memo[i + 1];
        bool flag1 = false, flag2 = false;
        //トポロジカルソートしたとなり通しの順序が変わることがあるかを調べる
        for(auto tmp : G[a]){
            if(tmp == b){//a -> bの辺が存在
                flag1 = true; break;
            }
        }
        if(flag1) continue;
        for(auto tmp : G[b]){
            if(tmp == a){//b -> aの辺が存在
                flag2 = true; break;
            }
        }

        if(!flag1 == !flag2){
            printf("1\n"); return 0;
        }
    }
    printf("0\n");
    return 0;
}