Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 终于过了，死循环N次，附代妈，给一组数据，另我觉得我的代妈扔然有bug

Posted by KatrineYang at 2016-07-22 19:34:04 on Problem 1236 and last updated at 2016-07-22 19:51:12
```#include <iostream>
#include <stdio.h>
using namespace std;

int MX(int a, int b){
if(a > b) return a;
return b;
}

int main() {
bool graph[101][101] = {false};
int N;
scanf("%d", &N);
for(int i = 1; i <= N; i++){
int temp;
while(1){
scanf("%d", &temp);
if(temp == 0) break;
graph[i][temp] = true;
}
}
bool valid[101];
int prev[101][101] = {0};
for(int i = 1; i <= N; i++) valid[i] = true;
//floid求圈
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(graph[i][j]) prev[i][j] = i;
}
}
//scout << prev[18][1] << endl;
for(int k = 1; k <= N; k++){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
if(i == j || graph[i][j]) continue;
if(graph[i][k] && graph[k][j]){
prev[i][j] = prev[k][j];
graph[i][j] = true;
}
}
}
}
//cout << 1 << endl;
bool quan = true;
//int cs = 0;
while(quan){
/*
for(int i = 1; i <= N; i++){
cout << i << ": ";
for(int j = 1; j <= N; j++){
cout << prev[i][j] << " ";
}
cout << endl;
}
//cout << cs << endl;
* */

//cs++;
quan = false;
bool beisuo[101] = {false};
int suoq[101];
int liuxia;
int cnt = 0;
for(int i = 1; i < N; i++){
//cout << i << endl;
if(!valid[i]) continue;
for(int j = i+1; j <= N; j++){
if(!valid[j]) continue;
if(graph[i][j] && graph[j][i]){
//cout << i << " " << j << endl;
int idx = i;
while(idx != j){
//cout << idx << endl;
beisuo[idx] = true;
suoq[cnt] = idx;
cnt ++;
idx = prev[j][idx];
}
idx = j;
while(idx != i){
//cout << idx << endl;
beisuo[idx] = true;
suoq[cnt] = idx;
cnt ++;
idx = prev[i][idx];
}
quan = true;
liuxia = i;
goto tush;
}
}
}
//cout << 1 << endl;
tush:
//cout << cnt << endl;
//for(int i = 1; i <= N; i++) cout << i << ": " << beisuo[i] << " "; cout << endl;
//for(int i = 0; i < cnt; i++) cout << suoq[i] << " "; cout << endl;
//cout << 1 << endl;
if(!quan) break;
int prev_temp[101][101] = {0};
//bool c19 = false;
//cout << "16,1:" << graph[16][1] << endl;
for(int i = 1; i <= N; i++){
if(!valid[i]) continue;
for(int j = 1; j <= N; j++){
if(j == i || !valid[j] || !graph[i][j]) continue;
if(!beisuo[i] && beisuo[j]) {
graph[i][liuxia] = true;
int idx = j;
while(beisuo[idx]){
//cout << i << " " << j << endl;
//if(cs == 1 && j == 1 && i == 19){ cout << idx << endl;}
idx = prev[i][idx];
//if(cs == 1 && j == 1 && i == 19){ cout << idx << endl;}

}
if(prev_temp[i][liuxia] == 0 || j == liuxia) prev_temp[i][liuxia] = idx;
//if(!c19) cout << prev_temp[19][1] << "_" << i << " " << j << endl;
//if(cs == 1 && j == 1 && i == 19){ cout << i << " " << liuxia << " " << idx << endl;}
}
if(beisuo[i] && !beisuo[j]) {
graph[liuxia][j] = true;
if(beisuo[prev[i][j]]) prev_temp[liuxia][j] = liuxia;
else prev_temp[liuxia][j] = prev[i][j];
//if(!c19) cout << prev_temp[19][1] << "#" << i << " " << j << endl;
}
if(!beisuo[i] && !beisuo[j]){
if(beisuo[prev[i][j]]) prev_temp[i][j] = liuxia;
else prev_temp[i][j] = prev[i][j];
//if(!c19) cout << prev_temp[19][1] << "*" << i << " " << j << endl;
}
//if(prev_temp[19][1] == 9) c19 = true;
}
}
for(int i = 1; i < cnt; i++) {
if(suoq[i] != liuxia) valid[suoq[i]] = false; //continue;
}

for(int i = 1; i <= N; i++){
if(!valid[i]) continue;
for(int j = 1; j <= N; j++){
if(!valid[j] || i==j || !graph[i][j]) continue;
prev[i][j] = prev_temp[i][j];
}
}

//cout << "N=" << N << endl;
//cout << &N << " " << suoq << endl;

//cout << 2333 << endl;
}
int ct = 0;
for(int i = 1; i <= N; i++) {
if(valid[i]) ct++;
}
/*
for(int i = 1; i <= N; i++){
if(!valid[i]) continue;
for(int j = 1; j <= N; j++){
if(!valid[j]) continue;
cout << graph[i][j] << " ";
}
cout << endl;
}*/
int wuru = 0, wuchu = 0;
for(int i = 1; i <= N; i++){
if(!valid[i]) continue;
int cnt = 0;
for(int j = 1; j <= N; j++){
if(valid[j] && i != j && graph[j][i]){
cnt++;
break;
}
}
if(cnt == 0) wuru ++;
}
for(int i = 1; i <= N; i++){
if(!valid[i]) continue;
int cnt = 0;
for(int j = 1; j <= N; j++){
if(valid[j] && i != j && graph[i][j]){
cnt++;
break;
}
}
if(cnt == 0) wuchu ++;
}
if(ct == 1) printf("1\n0\n");
else printf("%d\n%d\n", wuru, MX(wuru,wuchu));
return 0;
}

100
22 88 77 66 51 80 70 75 86 38 37 9 36 23 12 61 14 60 72 29 32 20 45 63 64 21 11 65 56 95 59 91 28 0
69 21 48 84 43 90 99 63 57 37 72 17 35 50 16 34 45 78 93 25 3 96 39 12 19 14 38 60 41 51 62 42 27 49 0
94 29 97 80 96 35 42 60 0
41 12 89 63 0
88 67 82 26 76 4 51 72 60 57 50 44 16 73 65 27 83 62 3 81 0
92 18 28 86 37 71 65 34 39 15 80 68 27 81 55 32 95 0
22 14 90 30 19 84 56 74 66 68 98 58 79 94 71 10 99 86 96 0
77 71 99 22 40 58 32 45 20 87 70 54 63 4 53 31 90 97 69 62 80 85 0
11 14 70 3 91 28 58 18 68 66 47 8 23 46 55 41 84 31 71 77 85 100 74 69 36 4 38 99 25 96 52 53 89 39 54 6 93 82 12 0
0
32 91 47 13 54 45 80 70 2 48 37 63 22 75 74 39 24 28 38 89 43 68 58 61 79 51 21 83 67 78 15 26 46 31 87 81 72 42 18 34 0
40 76 56 19 64 51 54 36 86 47 97 13 90 91 59 31 65 88 24 15 58 53 42 89 84 80 92 0
65 84 82 67 97 7 77 94 16 15 60 37 28 27 38 26 55 69 4 54 41 44 8 93 14 2 12 85 73 91 35 49 99 20 6 100 62 0
59 60 97 30 33 77 26 42 13 34 9 79 19 87 73 20 24 0
62 14 33 30 3 16 85 17 89 36 10 23 34 67 41 73 20 92 49 87 66 28 32 39 100 42 26 72 79 71 53 46 43 86 4 13 54 96 7 84 59 51 60 48 0
64 50 25 54 80 2 8 20 47 18 32 23 33 42 44 79 34 7 22 51 76 41 6 28 15 17 59 84 83 0
8 7 63 51 0
55 95 64 6 86 90 41 37 50 36 70 13 73 80 47 38 93 25 66 65 96 45 68 1 30 10 34 23 54 60 0
39 36 11 81 12 99 1 46 60 88 13 41 82 94 20 73 34 16 93 70 55 77 15 43 89 30 72 69 28 21 29 24 64 32 5 0
22 27 93 65 33 0
3 51 2 25 72 58 62 17 57 47 74 33 8 46 48 89 19 84 59 29 78 44 88 93 87 0
27 13 12 29 18 16 52 17 82 54 26 67 28 68 6 49 4 83 76 1 60 56 69 75 62 42 96 94 24 39 71 3 37 40 0
49 44 93 75 19 9 66 85 2 64 43 45 63 69 50 72 86 33 42 7 24 14 27 47 60 0
36 69 15 9 71 23 34 52 59 29 28 17 44 4 37 22 42 20 77 72 79 60 31 82 7 58 78 94 98 51 80 40 89 0
59 37 72 86 7 5 63 19 29 55 41 67 79 75 68 56 14 88 85 48 81 22 27 57 34 0
66 54 86 69 21 23 93 98 67 72 100 4 0
85 67 93 54 29 82 90 66 47 19 96 72 48 16 69 0
67 76 47 96 40 91 72 75 70 69 56 43 94 38 90 97 58 6 35 31 48 80 3 77 0
90 22 66 77 21 97 99 35 13 64 84 31 82 54 53 85 58 41 69 55 6 78 45 87 5 51 70 48 2 4 14 89 57 3 0
78 81 56 50 57 28 60 48 33 66 8 9 7 99 45 11 62 3 46 53 34 1 43 89 0
86 74 70 98 28 85 55 26 69 16 6 62 30 61 10 43 58 19 87 36 15 37 50 9 46 27 53 90 49 24 35 77 39 79 65 63 0
9 11 51 21 61 7 93 27 18 60 74 15 67 12 87 36 81 5 24 22 55 29 30 48 20 45 37 13 31 23 85 76 39 97 57 38 25 84 99 0
2 73 100 3 1 16 78 38 5 27 50 0
84 47 77 57 42 10 88 67 94 66 3 11 87 0
20 48 86 18 15 9 59 10 73 28 44 45 85 47 72 32 67 57 97 79 64 61 19 69 1 29 50 76 5 37 26 2 33 12 24 22 71 39 80 21 51 16 0
32 58 81 95 97 3 98 90 26 53 70 35 72 94 6 4 21 17 68 8 88 52 34 89 38 86 67 47 24 85 64 19 65 2 33 0
76 84 17 49 98 25 77 78 51 71 28 60 47 58 18 31 13 96 48 74 35 9 93 79 59 42 86 39 67 70 46 61 4 56 68 34 23 63 0
12 92 40 59 66 68 28 61 89 22 0
99 74 72 86 21 54 90 20 11 12 26 89 68 100 24 63 56 66 38 27 75 67 82 84 71 65 0
69 84 9 34 80 21 45 78 10 60 51 27 38 11 61 68 62 26 32 49 17 75 24 83 63 85 79 44 86 59 67 33 0
80 1 20 52 96 2 42 44 95 39 53 12 68 19 40 97 7 34 73 56 23 24 0
40 18 78 93 59 90 0
11 67 61 45 15 14 31 5 100 56 99 49 38 58 10 26 94 91 47 85 16 71 55 77 98 93 25 32 37 64 84 22 0
22 34 37 10 92 100 73 79 0
61 71 36 0
88 9 36 7 83 14 64 37 69 80 91 76 73 5 21 40 2 0
95 13 52 38 55 70 68 14 88 51 62 0
87 38 96 52 57 75 18 55 66 40 60 39 17 59 3 93 29 91 82 24 20 0
64 80 63 55 23 9 76 67 95 97 71 5 4 46 73 54 52 14 74 26 20 92 43 86 1 66 17 81 32 50 72 28 21 78 24 96 57 48 12 41 91 82 70 90 15 31 18 0
33 83 96 95 76 34 22 2 98 58 66 81 40 12 55 51 41 90 19 48 64 57 30 78 100 88 43 86 62 99 49 5 72 75 97 52 32 89 87 31 11 79 0
34 60 44 43 20 96 1 42 58 97 77 4 10 26 37 7 87 45 67 98 29 78 93 63 99 17 55 65 81 84 28 38 69 89 0
76 90 78 66 15 18 68 96 28 71 55 43 20 50 51 49 42 7 25 36 57 72 6 88 61 63 14 46 65 21 12 79 38 73 89 3 64 59 23 54 77 0
73 90 4 39 91 97 65 41 96 81 1 68 62 49 20 76 63 66 25 84 98 16 29 24 88 86 45 57 9 46 61 27 32 7 40 35 36 11 8 0
92 11 31 83 28 32 61 39 90 94 60 88 65 0
22 89 75 99 40 66 24 65 83 31 2 0
9 1 64 75 55 67 2 94 100 78 74 53 25 28 18 91 40 66 98 14 50 21 49 27 20 63 0
3 24 14 79 100 75 52 28 2 0
20 61 25 78 34 93 44 47 99 87 19 67 41 53 96 79 7 24 39 10 56 74 21 0
82 28 65 92 95 44 91 8 46 18 78 70 62 23 14 20 39 41 45 94 88 38 55 30 4 69 84 97 64 36 2 83 5 89 26 72 87 11 19 75 58 54 98 60 24 86 6 9 31 0
63 96 48 36 41 89 81 34 37 99 7 76 5 61 80 71 40 22 49 13 53 55 0
15 1 28 98 14 27 75 81 41 91 21 0
75 87 14 80 63 35 54 39 19 78 32 61 84 34 4 22 59 41 16 99 33 64 37 86 31 93 95 36 94 6 91 76 50 25 45 42 44 79 0
96 90 23 61 20 7 91 1 44 97 48 60 21 50 52 36 4 15 69 79 28 41 55 99 56 70 35 57 92 66 62 25 75 84 33 51 100 67 88 49 18 72 68 43 42 8 2 0
91 97 46 63 95 40 8 49 10 45 73 87 3 25 12 53 9 21 14 82 43 89 31 13 70 1 84 83 68 30 39 52 33 55 72 90 85 98 58 74 88 61 69 77 24 0
82 94 22 98 47 87 67 96 30 32 46 26 92 58 19 17 9 25 51 20 95 31 29 14 80 72 0
50 34 81 97 48 42 23 2 84 82 49 18 22 85 0
53 23 56 87 44 41 35 72 29 43 63 11 32 94 25 90 80 17 40 78 12 0
57 21 97 35 65 12 91 37 0
53 85 33 41 73 60 71 72 49 19 91 55 63 52 66 22 14 70 47 16 64 74 77 40 3 88 45 81 97 78 98 42 1 18 6 28 13 94 27 56 83 86 0
57 44 24 37 99 41 7 22 39 34 45 51 4 96 97 48 85 10 100 17 92 67 53 32 60 35 76 72 26 80 30 47 0
23 70 50 14 19 17 42 93 87 76 94 99 49 27 59 34 40 54 65 35 13 11 92 18 91 15 0
64 85 26 80 88 17 56 41 69 7 63 20 81 84 39 90 33 2 14 78 27 86 96 76 31 8 77 18 49 10 21 50 89 5 47 0
61 68 30 47 29 56 41 14 65 44 62 75 76 27 36 69 96 6 63 21 19 31 99 89 28 10 82 26 8 86 7 60 66 72 0
94 45 29 1 8 23 44 37 5 96 84 79 57 0
36 73 28 3 30 0
30 9 29 58 24 70 48 74 73 53 95 21 63 55 33 14 98 50 0
98 96 86 0
91 26 39 80 45 19 70 52 77 31 54 72 44 68 67 59 82 92 25 69 36 8 34 46 18 99 89 23 85 73 56 21 30 55 60 66 12 47 84 0
99 8 15 56 81 90 46 17 97 96 35 13 26 71 28 57 69 18 30 22 53 44 74 9 78 75 85 40 33 6 14 32 2 31 7 47 94 61 38 0
21 86 42 96 27 94 68 65 0
78 43 84 79 64 69 9 83 71 99 96 23 57 80 68 90 13 59 5 67 7 70 63 22 26 73 97 0
38 0
100 70 12 27 44 19 65 71 39 55 25 68 5 93 21 82 54 22 10 63 24 0
46 2 7 51 33 91 74 61 88 13 94 69 9 55 92 52 43 28 64 60 79 99 40 35 29 32 30 62 89 53 87 6 100 98 85 26 86 23 83 19 39 71 0
93 96 38 43 16 4 33 52 20 66 87 17 40 7 95 74 0
55 68 58 80 21 27 5 17 92 49 20 84 30 45 52 65 23 51 69 53 85 41 57 70 67 34 24 60 13 7 88 35 79 72 95 19 28 29 71 98 97 1 38 0
49 36 8 85 25 78 91 23 61 68 55 65 19 9 14 95 24 82 46 29 94 7 12 15 37 99 11 31 88 58 51 30 83 44 34 74 22 59 69 79 86 96 33 39 0
66 76 65 91 50 4 59 15 54 27 38 1 86 80 89 39 43 75 64 21 2 42 78 12 87 90 44 92 20 34 24 32 93 67 85 100 19 57 0
24 79 10 40 13 99 57 76 45 85 93 97 25 3 62 17 74 39 54 36 0
80 35 39 27 54 12 20 0
1 21 27 50 59 40 25 0
48 39 40 52 26 21 85 70 58 83 35 65 13 10 34 44 81 27 32 89 19 24 72 56 1 80 12 45 59 73 30 11 71 5 0
72 100 68 10 28 6 61 47 34 80 16 98 35 64 15 0
60 37 82 64 40 29 76 27 90 98 66 35 6 5 10 45 91 88 22 7 59 85 39 97 13 56 75 51 87 0
71 7 39 35 88 80 51 1 22 86 14 73 29 10 17 34 94 89 0
95 32 78 91 72 0
17 68 59 40 44 84 65 20 16 56 82 86 95 92 96 91 74 21 35 46 93 45 26 39 81 32 2 79 30 50 83 75 29 78 28 22 67 49 34 52 99 15 10 8 60 88 41 1 71 0
73 81 40 8 27 13 45 97 50 34 1 35 5 14 87 67 10 68 77 76 39 90 65 63 72 58 57 17 32 0
20 92 8 22 95 52 93 34 56 55 19 81 84 63 54 10 11 12 69 1 33 50 64 5 85 13 28 98 58 0
28 52 56 91 83 87 62 20 60 27 11 29 33 6 4 38 59 16 85 72 69 96 23 17 95 65 32 71 42 35 40 0
```

Followed by: