結果

問題 No.2301 Namorientation
ユーザー AngrySadEight
提出日時 2023-03-16 16:14:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 786 ms / 3,000 ms
コード長 3,480 bytes
コンパイル時間 1,283 ms
コンパイル使用メモリ 98,216 KB
最終ジャッジ日時 2025-02-11 11:51:25
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> B(N);
    for (int i = 0; i < N; i++){
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }
    map<pair<int,int>, int> mp;
    for (int i = 0; i < N; i++){
        mp[pair<int,int>(A[i], B[i])] = i;
    }

    vector<vector<int>> graph(N, vector<int>(0));
    for (int i = 0; i < N; i++){
        graph[A[i]].push_back(B[i]);
        graph[B[i]].push_back(A[i]);
    }
    
    vector<bool> tag(N, true);
    vector<int> count(N, 0);
    for (int i = 0; i < N; i++){
        count[A[i]]++;
        count[B[i]]++;
    }
    
    //ループ以外の辺を削除するために BFS
    vector<bool> isvisited(N, false);
    queue<int> que;
    for (int i = 0; i < N; i++){
        if (count[i] == 1) que.push(i);
    }
    while(que.size()){
        int p = que.front();
        que.pop();
        if (isvisited[p]){
            continue;
        }
        isvisited[p] = true;
        for (int x: graph[p]){
            tag[mp[pair<int,int>(min(p, x), max(p, x))]] = false;
            count[x]--;
            if (count[x] == 1){
                que.push(x);
            }
        }
    }
    vector<int> ans(N);

    // ループのみのグラフ
    vector<vector<int>> graph2(N, vector<int>(0));
    int start = -1;
    for (int i = 0; i < N; i++){
        if (tag[i]){
            start = A[i];
            graph2[A[i]].push_back(B[i]);
            graph2[B[i]].push_back(A[i]);
        }
    }

    // ループの中だけをみる
    for (int i = 0; i < N; i++) isvisited[i] = false;
    
    int now = start;
    while(true){
        isvisited[now] = true;
        bool seen = false;
        for (int i = 0; i < graph2[now].size(); i++){
            if (isvisited[graph2[now][i]]){
                continue;
            }
            seen = true;
            if (graph2[now][i] > now){
                ans[mp[pair<int,int>(now, graph2[now][i])]] = 1;
            }
            else{
                ans[mp[pair<int,int>(graph2[now][i], now)]] = 0;
            }
            now = graph2[now][i];
            break;
        }
        if (!seen){
            for (int i = 0; i < graph2[now].size(); i++){
                if (graph2[now][i] == start){
                    if (graph2[now][i] > now){
                        ans[mp[pair<int,int>(now, graph2[now][i])]] = 1;
                    }
                    else{
                        ans[mp[pair<int,int>(graph2[now][i], now)]] = 0;
                    }
                }
            }
            break;
        }
    }

    // ループの外だけで BFS

    
    for (int i = 0; i < N; i++){
        if (isvisited[i]){
            que.push(i);
            while(que.size()){
                int p = que.front();
                que.pop();
                for (int x: graph[p]){
                    if (isvisited[x]) continue;
                    isvisited[x] = true;
                    if (p > x){
                        ans[mp[pair<int,int>(x, p)]] = 1;
                    }
                    else{
                        ans[mp[pair<int,int>(p, x)]] = 0;
                    }
                    que.push(x);
                }
            }
        }
    }
    for (int i = 0; i < N; i++){
        if (ans[i] == 1) cout << "->" << endl;
        else cout << "<-" << endl;
    }
    
    return 0;
}
0