计算改变边方向以使图成为无环图的方法数

#include <iostream>
#include <vector>

struct Edge {
    int source, destination;
};

// Function to check if the graph becomes acyclic
bool isAcyclic(const std::vector<Edge>& edges, std::vector<bool>& visited);

// Depth-first search to detect cycles
bool dfs(const std::vector<Edge>& edges, std::vector<bool>& visited, std::vector<bool>& recursionStack, int vertex) {
    visited[vertex] = true;
    recursionStack[vertex] = true;

    for (const Edge& edge : edges) {
        if (edge.source == vertex) {
            int destination = edge.destination;
            if (!visited[destination] && dfs(edges, visited, recursionStack, destination))
                return true;
            else if (recursionStack[destination])
                return true;
        }
    }

    recursionStack[vertex] = false;
    return false;
}

// Function to check if the graph becomes acyclic
bool isAcyclic(const std::vector<Edge>& edges, std::vector<bool>& visited) {
    int numVertices = visited.size();
    std::vector<bool> recursionStack(numVertices, false);

    for (int i = 0; i < numVertices; ++i) {
        if (!visited[i] && dfs(edges, visited, recursionStack, i))
            return false;
    }

    return true;
}

// Function to count the ways to change edge directions to make the graph acyclic
int countAcyclicConfigurations(std::vector<Edge>& edges, std::vector<bool>& directed, int index) {
    int numWays = 0;
    int numEdges = edges.size();

    if (index == numEdges) {
        if (isAcyclic(edges, directed))
            return 1;
        else
            return 0;
    }

    // Change direction of edge and backtrack
    directed[index] = true;
    numWays += countAcyclicConfigurations(edges, directed, index + 1);

    // Restore direction of edge and backtrack
    directed[index] = false;
    numWays += countAcyclicConfigurations(edges, directed, index + 1);

    return numWays;
}

int main() {
    // Example usage
    int numVertices = 4;
    std::vector<Edge> edges = {
        {0, 1},
        {1, 2},
        {2, 3},
        {3, 0}
    };
    int numEdges = edges.size();

    // Initialize directed array with false values
    std::vector<bool> directed(numEdges, false);

    int numAcyclicConfigurations = countAcyclicConfigurations(edges, directed, 0);
    std::cout << "Number of ways to change edge directions to make the graph acyclic: " << numAcyclicConfigurations << std::endl;

    return 0;
}