Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 08.10.2012, 20:39   #1
Lodyr
Пользователь
 
Регистрация: 15.12.2009
Сообщений: 69
По умолчанию Проверка графа на ацикличность

Код:
#include<fstream>
#include<sstream>
#include<iostream>
#include<string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
ifstream in("in.txt");
ofstream out("out.txt");

string s;
int n,temp;
vector<vector<int>> vec(n);
int m=0;
stack <int> Stack;
int* was =  new int[n];
int** arr =  new int*[n];

void dfs(int i)
{
		if (was[i]==1)
		{
			m++;
			return;
		}

		if (was[i]!=0)
		{
				return;
		}

		was[i]=1;
		for (int j=0;j<n;j++)
		{
			if (arr[i][j]==1)
				{
					dfs(j);
				}
		}
		was[i]=2;
}

int main()
{   
    in>>n; 
	for(int i=0;i<n;i++)
        {
            was[i]=0;
        }

    for(int i = 0; i<n;i++)
		{ 
			arr[i] = new int [n];
		}
	for(int i=0;i<n; i++)
   {
            for(int j=0;j<n;j++)
        {
            arr[i][j]=0;
        }
    }


    in.get();
    vec.resize(n);
    for(int i=0;i<n;i++)
    {
        std::stringstream ss;
        getline(in,s);
        ss<<s;
        while(!ss.eof())
        {
            ss>>temp;
            vec[i].push_back(temp);
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<vec[i].size();j++)
            out<<vec[i][j]<<" ";
			out<<endl;
    }
	out<<endl;
	int k;
	for(int i=0;i<n;i++)
    {
        for(int j=0;j<vec[i].size();j++)
            if (vec[i][j]!=0) 
			{
				k=vec[i][j];
				arr[i][k-1]=1;
			}
    }
	
	for(int i=0;i<n; i++)
    {
            for(int j=0;j<n;j++)
        {
            out<<arr[i][j]<<" ";
        }
		out<<endl;
    }
	out<<endl;

	for(int i=0; i<n; i++)
	{
		out<<was[i]<<" ";
	}
	out<<endl;
	
	for(int i=0; i<n; i++)
	{
		if (was[i]==0) 
			{
				dfs(i);
			}
	}
	out<<m<<endl;
	if (m==0) 
		out<<"NET CICLE"<<endl;
	if (m!=0)
		out<<"YES CICLE"<<endl;

	in.close();
	out.close();
    return 0;
}
в файле in.txt лежит список смежности
например
4
2 3 0
1 3 4 0
1 2 0
2 0
в проге я перехожу к матрице смежности, но никак не могу понять почему у меня всегда m меняется...
мол нет ни одного случая когда нет цикла в графе....
Lodyr вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Проверка на ацикличность Lodyr Помощь студентам 3 07.10.2012 15:51
создание графа по матрице и поиск кратчайшего пути из одного графа в другой lexflax Общие вопросы C/C++ 1 06.09.2012 07:32
по заданной матрице смежности простого графа построить каркас этого графа с использованием поиска вширь d1m2o3n4 Помощь студентам 0 22.06.2011 22:43
проверка системы циклов графа на линейную независимость Сергеевна Помощь студентам 0 13.04.2011 22:48
Проверка системы циклов графа на линейную независимость Сергеевна Общие вопросы по Java, Java SE, Kotlin 0 13.04.2011 00:11