Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
White_volf
4 / 4 / 0
Регистрация: 13.12.2012
Сообщений: 20
29.05.2014, 14:34     Для графа определить его двудольность и вывести обе доли (исправить программу) #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;
}
задание:
для графа определить его двудольность и вывести обе доли...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.05.2014, 14:34     Для графа определить его двудольность и вывести обе доли (исправить программу)
Посмотрите здесь:

C++ Для ориентированного графа определить полустепень захода и исхода для каждой из вершин
Массивы, нужно определить минимальный элемент, вывести его значение и индекс... C++
Для заданного натурального пятизначного числа выполнить перестановку его крайних чётных цифр (исправить ошибки) C++
C++ Определить степени вершин графа и если граф однородный - вывести степень однородности
C++ Определить текущий день недели, год, месяц, число, а также текущее время-часы, минуты, секунды, сотые доли секунды.
C++ Вводятся 2 строки. Перевернуть обе строки, склеить и вывести
C++ Составить программу, которая находит наибольшее значение доли трехзначного числа к сумме его цифр
Функция для расчета доли C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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<<' ';
        }
    }
 
}
Yandex
Объявления
29.05.2014, 16:09     Для графа определить его двудольность и вывести обе доли (исправить программу)
Ответ Создать тему
Опции темы

Текущее время: 11:34. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru