(2-SAT・強連結成分分解)POJ-3683-Priest John’s Busiest Day

問題URL→http://poj.org/problem?id=3683

問題概要
蟻本に載っている問題なので蟻本を見た方が速い。
2-SATの問題は初めて解いた。
2-SATは強連結成分分解で解けるらしい。

//#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
//#define int long long
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
const int INF = 1e9;

int V;  //頂点数
vector<int> G[10101];
vector<int> rG[10101];  //辺の向きを逆にしたグラフ
vector<int> vs;         //帰りがけ順の並び
bool used[10101];
int cmp[10101];         //属する強連結成分のトポロジカル順序「

void add_edge(int from, int to)
{
    G[from].push_back(to);
    rG[to].push_back(from);
}

void dfs(int v)
{
    used[v] = true;
    REP(i,G[v].size()) {
        if (!used[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);    //帰りがけ順
}

void rdfs(int v, int k)
{
    used[v] = true;
    cmp[v] = k;
    REP(i,rG[v].size()) {
        if (!used[rG[v][i]]) rdfs(rG[v][i], k);
    }
}

int scc()
{
    memset(used, 0, sizeof used);
    vs.clear();
    REP(v,V) {
        if (!used[v]) dfs(v);
    }
    memset(used, 0, sizeof used);
    int k = 0;
    for (int i=vs.size()-1; i>=0; i--) {
        if (!used[vs[i]]) rdfs(vs[i], k++);
    }
    return k;
}

int N;
int S[1010], T[1010], D[1010];

signed main()
{
    cin >> N;
    REP(i,N) {
        int SH, SM, TH, TM;
        char c;

        cin >> SH >> c >> SM >> TH >> c >> TM >> D[i];
        S[i] = 60 * SH + SM;
        T[i] = 60 * TH + TM;
    }

    V = N * 2;
    for (int i=0; i<N; i++) {
        for (int j=0; j<i; j++) {
            if (min(S[i] + D[i], S[j] + D[j]) > max(S[i], S[j])) {
                add_edge(i, N + j);
                add_edge(j, N + i);
            }
            if (min(S[i] + D[i], T[j]) > max(S[i], T[j] - D[j])) {
                add_edge(i, j);
                add_edge(N + j, N + i);
            }
            if (min(T[i], S[j] + D[j]) > max(T[i] - D[i], S[j])) {
                add_edge(N + i, N + j);
                add_edge(j, i);
            }
            if (min(T[i], T[j]) > max(T[i] - D[i], T[j] - D[j])) {
                add_edge(N + i, j);
                add_edge(N + j, i);
            }
        }
    }
    scc();

    for (int i=0; i<N; i++) {
        if (cmp[i] == cmp[N+i]) {
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;
    REP(i,N) {
        if (cmp[i] > cmp[N+i]) {
            printf("%02d:%02d %02d:%02d\n", S[i] / 60, S[i] % 60, (S[i] + D[i]) / 60, (S[i] + D[i]) % 60);
        } else {
            printf("%02d:%02d %02d:%02d\n", (T[i] - D[i]) / 60, (T[i] - D[i]) % 60, T[i] / 60, T[i] % 60);
        }
    }
}