Два года назад решал задачу 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;
} |
|
(
