Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
White_volf
4 / 4 / 0
Регистрация: 13.12.2012
Сообщений: 20
#1

Для графа определить его двудольность и вывести обе доли (исправить программу) - C++

29.05.2014, 14:34. Просмотров 661. Ответов 1
Метки нет (Все метки)

помогите исправить программу!
запускается, на файл вывода пуст... а когда раскоментирываю - не компилруется...

вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <fstream>
#include<iostream>
#include <string>
#include<vector>
using namespace std;
vector < vector <int> > g; // Г§Г*Г¤Г*Г*Г*ûé ГЈГ°Г*Гґ
vector <int> used; // Г¬Г*Г±Г±ГЁГў ìåòîê
vector <int> c;
vector <vector <int> > components;
int n; // êîëè÷åñòâî âåðøèГ*
int col=1;
ifstream fin("input.txt");
ofstream fout("output.txt");
int dfs(int v)
{
used[v] = 1; //v-Г±ГІГ*ðòîâГ*Гї âåðøèГ*Г*
if (col==1){col++;}
else {col--;}
for (int i = 0; i < (int)g[v].size(); i++)
{
if (!used[g[v][i]])
{
if (c[g[v][i]]!=c[v])
{ 
c[v]=col;
return 1;
}
else
{
fout<<"N";
return 0;
}
}
}
}
int findC()
{
used.resize(n + 1, 0); // îáГ*óëÿåì Г¬Г*Г±Г±ГЁГў ìåòîê-âìåñòî 20 ìåòîê Г±ГІГ*ëî 0
for (int i = 1; i <= n; i++) //ïðîáåãГ*ГҐГ¬ ГЇГ® ГўГ±ГҐГ¬ âåðøèГ*Г*Г¬
{
if (!used[i])
{
int cu=dfs(i);
if (cu==0)
{return 0;}
}
}
fout<<"Y";
/*vector <int> r2={0};
vector <int> r1={0};
r1.push_back(1);
r2.push_back(v);
int ci1=1;
int ci2=0;
r1[0]=1;
for (int k = 0; k < n; k++) {
if(c[k]==l){r1[ci1]=k+1; ci1++;}
else {r1[ci2]=k+1; ci2++;}
}
int coo1=0;
int coo2=0;
while(r1[coo1]!=0)
{
fout«r1[coo1]<" ";
coo1++;
}
fout«endl;
while(r1[coo2]!=0)
{
fout«r2[coo2]<" ";
coo2++;
}*/
return 1;
}
int main()
{
string lines;
if (fin.is_open())
{
//ïîñòðî÷Г*îå Г·ГІГҐГ*ГЁГҐ ГґГ*éëГ*
string buff;
fin >> n;
vector<int> v;
g.push_back(v);
for (int i = 0; i < n; i++)
{
vector <int> v;
int k = 0;
fin >> k; //Г§Г*ГЇГЁГ±Г*ëè Гў ГЄ âåðøèГ*Гі ГЁГ§ ГґГ*éëГ*
while (k != 0) { //ïîêГ* Г*ГҐ âñòðåòèëñÿ 0 ГўГ® âõîäГ*îì ГґГ*éëå
v.push_back(k); //Г§Г*ГЇГЁГ±Г*ëè Гў âåêòîð âåðøèГ*Гі
fin >> k; //Г±Г·ГЁГІГ*ëè ñëåäóþùóþ âåðøèГ*Гі
}
g.push_back(v); //Г§Г*ГЇГЁГ±Г*ëè ГўГ±ГҐ Гў ГЈГ°Г*Гґ
}
fin.close();
int re =findC();
}
else
cout << "Error! Open file!\n";
system("pause");
return 0;
}
задание:
для графа определить его двудольность и вывести обе доли...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2014, 14:34
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Для графа определить его двудольность и вывести обе доли (исправить программу) (C++):

Составить программу, которая находит наибольшее значение доли трехзначного числа к сумме его цифр - C++
Здравствуйте, помогите с заданием: А то я его что-то понял плохо...

Двудольность графа - C++ Builder
Требуется проверить граф на двудольность методом поиска в глубину либо в ширину на С++ Опишите, пожалуйста, алгоритм по шагам

Проверка графа, заданного матрицей смежности, на двудольность - C++/CLI WinForms
Здравствуйте!!! Подскажите пожалуйста алгоритм, с помощью которого можно проверить граф, заданный матрицей смежности, на двудольность....

Исправить программу. Найти самое длинное слово и вывести его на экран - Pascal ABC
Вводится строка слов, разделенных пробелами. Найти самое длинное слово и вывести его на экран. Случай, когда самых длинных слов может быть...

Определить и вывести на экран множество символов входящих одновременно в обе строки g и f - Pascal
Здравствуйте, мне нужно решить следующую задачу: Ввести две строки g и f. Определить и вывести на экран множество символов входящих...

Определить и вывести на экран множество символов входящих одновременно в обе строки - Free Pascal
Ввести две строки g и f. Определить и вывести на экран множество символов входящих одновременно в обе строки g и f.

1
grikukan
61 / 61 / 21
Регистрация: 23.09.2012
Сообщений: 212
29.05.2014, 16:09 #2
Что-то Вы не то сделали...
Это пишется примерно так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
#include<vector>
#include<memory.h>
using namespace std;
long n,m;
vector<long> graph[100007];//сам граф
long visited[100007];
bool possible=true; // граф двудолен
void dfs(long v,int c) // v - вершина, c-цвет
{
    visited[v]=c; // красим вершину
    for(int j=0;j<graph[v].size();j++)
    {
        if(visited[graph[v][j]]==0) //если вершина не покрашена
        {
            long new_colour;
            if(c==1) // Меняем цвет
            {
                new_colour=2;
            }
            else
            {
                new_colour=1;
            }
            dfs(graph[v][j],new_colour); // Идем в другую вершину
        }
        if(visited[graph[v][j]]==c) // ребро соединяет вершины одинакового цвета,граф не двудолен
        {
            possible=false; // Не двудолен - значит не двудолен
        }
    }
}
 
int main()
{
    cin>>n>>m; // n- количество вершин, m- количестов ребер
    memset(visited,sizeof(visited),0);
    for(int i=1;i<=m;i++)
    {
        long p,q;
        cin>>p>>q; // читаем ребро
        graph[p].push_back(q);
        graph[q].push_back(p);
    }
    for(int i=1;i<=n;i++)
    {
        if(visited[i]==0) // Если мы еще не посетили вершину
        {
            dfs(i,1); // Идем ее красить
        }
    }
    if(!possible) // Граф не двудолен, печалька
    {
        cout<<"Graph isn't biparate :("<<endl;
        return 0;
    }
    cout<<"Graph is biparate :)"<<endl;
    cout<<"The first part of graph: "<<endl;
    for(int i=1;i<=n;i++)
    {
        if(visited[i]==1) // Вериша покрашена в первый цвет
        {
            cout<<i<<' ';
        }
    }
    cout<<endl;
    cout<<"The second part of graph: "<<endl;
    for(int i=1;i<=n;i++)
    {
        if(visited[i]==2) // Вериша покрашена во второй цвет
        {
            cout<<i<<' ';
        }
    }
 
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.05.2014, 16:09
Привет! Вот еще темы с ответами:

Нахождение фактора графа и остова графа для некоторого произвольного графа (5-6 вершин) - Дискретная математика
Форумчане прошу помощь в выполнение задания по деск. мат. Задание: Нахождение фактора графа и остова графа для некоторого произвольного...

Открываются обе формы, как исправить? - Visual Basic
открываются обе формы..форма &quot;комедии&quot; и Форма &quot;комедии_сша&quot; как исправить Private Sub Command1_Click() If Combo2.Text = &quot;Êîìåäèÿ&quot;...

Для массива Х(10) определить, является ли сумма его элементов четным числом и вывести на печать “да” или “нет” - Delphi
Для массива Х(10) определить, является ли сумма его элементов четным числом и вывести на печать “да” или “нет”;

Для каждого нечетного столбца матрицы определить максимум, и вывести на экран сам элемент и его индексы - Delphi
Дано: с клавиатуры вводятся два целых числа – М и К. 1&lt;M&lt;10, 1&lt;K&lt;10. (М – число строк, К – число столбцов) Требуется: сгенерировать...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru