Участник:Taranov srg/Help the Commander in Chief

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/KFSTB/

C++ 14 clang 8.0

#include <cstdio>
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int MAXN = 100010;
const int MOD = 1000000007;
 
int n;
vector<int> g[MAXN];
bool used[MAXN];
vector<int> ans,values;
 
void dfs (int v) {
    used[v] = true;
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (!used[to])
            dfs (to);
    }
    ans.push_back (v);
}
 
void topological_sort() {
    for (int i=0; i<=n; ++i)
        used[i] = false;
    ans.clear();
    for (int i=0; i<=n; ++i)
        if (!used[i])
            dfs (i);
    reverse (ans.begin(), ans.end());
}
 
int main(){
    int d, c, b, s, t, v1, v2;
    ifstream input_file;
    scanf("%d",&d);
    while (d--){
        scanf("%d %d %d %d", &n, &b, &s, &t);
        for (int i=0; i<=n; i++) for (int j=0; j<=n; ++j) g[i].push_back(0);
        while (b--){
            // input_file >> v1 >> v2;
            scanf("%d %d", &v1, &v2);
            g[v1][v2] = 1;
        }
        topological_sort();
        reverse (ans.begin(), ans.end());
        for (int i=0; i<=n; i++) values.push_back(0);
        values[s] = 1;
        for (int i=1; i<=n; ++i){
            if (ans[i] == t){
                printf("%d\n", values[t]);
                break;
            }
            if (!values[ans[i]]) continue;
            for (int j=i+1; j<=n; ++j){
                if (g[ans[i]][ans[j]]){
                    values[ans[j]] += values[ans[i]];
                    values[ans[j]] %= MOD;
                }
            }
        }
        values.clear();
        while (n--) g[n].clear();
    }
    return 0;
}