VPF::Алгоритм Косарайю - Форум программистов

Abbath1349

Дата 15.7.2012, 21:10 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 214
Регистрация: 16.6.2010

Репутация: нет
Всего: нет

Пытаюсь реализовать алгоритм Косарайю на С++ вроде все правильно написал, но не работает подскажите где ошибка?

Код


#include <queue>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <array>
using namespace std;
void print_vector_of_vectors(vector<vector<int>> c);
class SCCs
{
    void dfs(vector<int> graph[],bool used[],vector<int> res,int u)
    {
        used[u]=true;
        for(int v:graph[u])
            if(!used[v])
                dfs(graph,used,res,v);
        res.push_back(u);
    }
    public:
        vector<vector<int>> scc(vector<int> graph[],int size)
        {
            int n=size;
            vector<int> *reverseGraph=new vector<int>[n];
            for(int i=0;i<n;i++)
                for(int j:graph[i])
                    reverseGraph[j].push_back(i);
            bool *used=new bool[n];
            vector<int> order;
            for(int i=0;i<n;i++)
                if(!used[i])
                    dfs(graph,used,order,i);
            reverse(order.begin(),order.end());
            vector<vector<int>> components;
            for(int i=0;i<n;i++) used[i]=false;
            for(int u:order)
                if(!used[u])
                {
                    vector<int> component;
                    dfs(reverseGraph,used,component,u);
                    components.push_back(component);
                }
                return components;
        }

}
;

int main(){

    SCCs sc;
    vector<int> g[3];
    g[2].push_back(0);
    g[2].push_back(1);
    g[0].push_back(1);
    g[1].push_back(0);

    vector<vector<int>> components=sc.scc(g,3);
    print_vector_of_vectors(components);
    system("pause");
}
void print_vector_of_vectors(vector<vector<int>> c)
{
    int len=g.size();
    for(int i=0;i<len;i++)
    {
        for(int j=0;j<g[i].size();j++)
            printf("%d ",g[i][j]);
        printf("\n");
    }

}

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »