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

Жутко туплю на ACMP - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Программа управления аккаунтами http://www.cyberforum.ru/cpp/thread276034.html
Здраствуйте. У меня есть задача которую я немогу решить. Нада сделать в этой задаче чтобы можна было создавать, удалять, изменять аккаунты. Я сделал только управлением одного аккаунта, а мне нужно множество. Вот код который я сделал, да там много неправильно или граматических ошибок, но повторяюсь суть не в этом. Вот код программы, то что я уже сделал. Помогите пожалуйста очень нужно. #include...
C++ Следующая анаграмма строки в лексикографическом порядке Условие Для данного слова (последовательности строчных латинских букв) выведите следующее за ним (в лексикографическом порядке) слово, которое может быть получено из данного перестановкой букв (анаграмму). Если из данное слово уже является последним среди всех своих анаграмм, то необходимо вывести первую возможную (в лексикографическом порядке) анаграмму. Формат входных данных Задана... http://www.cyberforum.ru/cpp/thread275919.html
Комментарий к коду C++
Ребят,помогите кто нибудь вот программа: #include <iostream> using namespace std; void main() { int n; int factorial=1; cin>>n; if(n>12) return;
C++ Калькулятор
разработать кулькулятор, выполняющий арифметические операции над римскими цифрами, обеспечивающий перевод из римской системы в десятичную систему счисления
C++ Масив на С http://www.cyberforum.ru/cpp/thread275627.html
нада написать массив из чисел в котором будет считатся сума этих чисел
C++ Событие при ОТжатии клавиши Всем привет,Хотел бы узнать какой функцией из WinApi или OpenGL можно сделать событие при ОТжатии клавиши? На счет WM_KEYUP компилятор говорит что нельзя ее как-то там представить,хотя код брал с мсдн,есть альтернативы? подробнее

Показать сообщение отдельно
Veyron
 Аватар для Veyron
105 / 105 / 4
Регистрация: 02.06.2009
Сообщений: 579
14.04.2011, 09:21     Жутко туплю на ACMP
Два года назад решал задачу 151 на ********... Щас не могу вспомнить, чего не хватает и что лишнее...
Принцип: Проверяю все компоненты связности на двудольность и смотрю, чтобы их число было не более двух...
Код:
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
#include <fstream>
#include <queue>
 
using namespace std;
 
int N,M;
int gr[103][103];
bool F[103];
int C[103];
 
void init()
{
    for (int i=1;i<=102;i++)
        for (int j=1;j<=102;j++)
            gr[i][j]=1;
    for (int i=1;i<=102;i++)
    {
        F[i]=true;
        gr[i][i]=0;
        C[i]=-1;
    }
}
 
bool BFS(int v)
{
    F[v]=false;
    queue <int> Q;
    C[v]=0;
    Q.push(v);
    while (!Q.empty())
    {
        v=Q.front(); Q.pop();
        for (int i=1;i<=N;i++)
            if (F[i] && gr[v][i])
            {
                if (C[i]!=-1 && (C[i])%2 != (C[v]+1)%2)
                    return false;
                else
                {
                    C[i]=C[v]+1;
                    F[i]=false;
                    Q.push(i);
                }
            }
    }
    return true;
}
 
int ManyExists()
{
    for (int i=1;i<=N;i++)
        if (F[i]) 
            return i;
    return 0;
}
 
bool IsBinGr()
{
    int num=0;
    int r;
    while ((r=ManyExists())!=0)
    {
        num++;
        if(num>2) return false;
        if (!BFS(r)) return false;
    }
    return true;
}
 
int main()
{
    ifstream cin("INPUT.TXT");
    ofstream cout("OUTPUT.TXT");
    init();
    cin >> N >> M;
    for (int i=0;i<M;i++)
    {
        int x,y;
        cin >> x >> y;
        gr[x][y]=0;
        gr[y][x]=0;
    }
    if (!IsBinGr()) cout << "NO";
    else
        cout << "YES";
    return 0;
}
Пособите, пожалуйста с задачей.
Заранее спасибо!

Добавлено через 9 часов 57 минут
Бага найдена.
1. Неправильно был считан граф (получось дополнение до полного графа от исходного);
2. Косяк с проверкой двудольности;
3. Считать компоненты не обязательно.

Код:
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
#include <fstream>
#include <queue>
#include <string.h>
 
using namespace std;
 
int N,M;
int gr[103][103];
bool F[103];
int C[103];
 
void init()
{
                memset(gr, 0, sizeof(gr));
    for (int i=1;i<=102;i++)
    {
        F[i]=true;
        C[i]=-1;
    }
}
 
bool BFS(int v)
{
    F[v]=false;
    queue <int> Q;
    C[v]=1;
    Q.push(v);
    while (!Q.empty())
    {
        v=Q.front(); Q.pop();
        F[v]=false;
        for (int i=1;i<=N;i++)
            if (gr[v][i]==1)
            {
                if (C[i]!=-1 && ((C[i])%2 == (C[v])%2))
                    return false;
                else
                {
                    C[i]=C[v]+1;
                    if (F[i]==true)
                    Q.push(i);
                }
            }
    }
    return true;
}
 
int ManyExists()
{
    for (int i=1;i<=N;i++)
        if (F[i]) 
            return i;
    return 0;
}
 
bool IsBinGr()
{
    int r;
    while ((r=ManyExists())!=0)
    {
        if (!BFS(r)) return false;
    }
    return true;
}
 
int main()
{
    ifstream cin("INPUT.TXT");
    ofstream cout("OUTPUT.TXT");
    init();
    cin >> N >> M;
    for (int i=0;i<M;i++)
    {
        int x,y;
        cin >> x >> y;
        gr[x][y]=1;
        gr[y][x]=1;
    }
    if (!IsBinGr()) cout << "NO";
    else
        cout << "YES";
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 21:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru