結果

問題 No.3499 I Love DAG
コンテスト
ユーザー aorinngo0606
提出日時 2026-04-19 09:00:46
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,433 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,232 ms
コンパイル使用メモリ 186,348 KB
実行使用メモリ 39,104 KB
平均クエリ数 489.63
最終ジャッジ日時 2026-04-19 09:01:36
合計ジャッジ時間 6,219 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other AC * 15 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
    // 入力を受け取る
    int N, M; cin >> N >> M;
    vector<vector<int>> G(N);   // グラフを表現する隣接リスト (終点のインデックスから、始点の番号を取り出す)
    vector<int> deg(N, 0);  // deg[v]：頂点 v の出次数
    // for(int i = 0; i < M; ++i) {
    //     int a, b; cin >> a >> b;
    //     // 通常のグラフとは逆で、G[b] に a を入れる
    //     G[b].push_back(a);
    //     // 頂点 a の出次数を 1 増やす
    //     deg[a]++;
    // }
    for(int i = 0;i < M;  ++i){
        int a,b; cin >> a >> b;
        a--; b--;
        G[b].push_back(a);
        deg[a]++;
        bool f = false;
        vector<int> deg_copy = deg;
        queue<int> que; // 探索候補の頂点番号を入れるキュー
        // 頂点 v = 0, 1, …, N-1 の順に
        for(int v = 0; v < N; ++v) {
            // 頂点 v の出次数が最初の時点で 0 ならば、キューに v を入れる
            if(deg_copy[v] == 0) {que.push(v);}
        }

        vector<int> order;  // トポロジカルソート順を格納するための配列
        // キューに要素が残っている限り
        while(que.size() > 0) {
            // キューの先頭要素 v を取り出し、配列 order に挿入する
            int v = que.front();
            que.pop();
            order.push_back(v);

            // 頂点 v に隣接している頂点 v2 について、
            for(auto v2 : G[v]) {
                // v2 の出次数を 1 減らして、もし出次数が 0 になったらキューに v2 を入れる
                deg_copy[v2]--;
                if(deg_copy[v2] == 0) {que.push(v2);}
            }
        }

        // 全ての頂点が order に含まれているかによって、答えを変える
        if(order.size() != N) {
            // order の要素数が N でなければ、order に含まれていない頂点があるので Yes
            f = false;
            G[b].pop_back();
            G[a].push_back(b);
            deg[a]--;
            deg[b]++;
            cout << 1 << endl;
        }
        else {
            // order の要素数が N であれば、すべての頂点が order に含まれているので No
            f = true;
            cout << 0 << endl;
        }
    }
    
    

	return 0;
}
0