796 - Critical Links

[prashantharshi]

a cut edge or bridge edge is not the part of any cycle
so for each edge u-v if there exists any desecdant of v (inclusive) which has a back edge on the ancestors of u (inclusive) then that edge is not back edge
http://ideone.com/rpPQdQ
i m getting WA
need hellp....
need to know wat AC soln gives for the test case
2
0 (1) 1
1 (0) 0

1
0 (1) 1

[lbv]

i m getting WA
need hellp....

Carefully read the "Output" section. You may try:

Input

Code: Select all

8
0 (3) 2 6 7
1 (1) 6
2 (2) 0 6
3 (1) 4
4 (2) 3 5
5 (1) 4
6 (3) 0 1 2
7 (1) 0

6
0 (1) 4
1 (2) 2 3
2 (3) 1 4 5
3 (1) 1
4 (2) 0 2
5 (1) 2

Output

Code: Select all

4 critical links
0 - 7
1 - 6
3 - 4
4 - 5

5 critical links
0 - 4
1 - 2
1 - 3
2 - 4
2 - 5

need to know wat AC soln gives for the test case
2
0 (1) 1
1 (0) 0

1
0 (1) 1

The output for the first case is:

Code: Select all

1 critical links
0 - 1

The second case is invalid.

[raj]

I dont know why sometimes question are not clear
in question: "The links are listed in ascending order according to their first element."

so it mean if the critical links are (4 - 2) , (1 - 2) , (1 - 5)
ans could be:
(1-2)
(1-5)
(4-2)
OR
(1-2)
(1-5)
(2-4)
OR
(1-5)
(1-2)
(4-2)
OR
(1-5)
(1-2)
(2-4)
OR.....

BUT, the accepted answer is only
(1-2)
(1-5)
(2-4)
why?

[brianfry713]

There is only one correct output: the smaller element of each link should be listed first, then sorted in ascending order.

[nafeeur_kuet]

Giving WA!! But why?!!

Code: Select all

Removed after AC.

[lighted]

Carefully read the "Output" section. You may try:

Input

Code: Select all

6
0 (1) 4
1 (2) 2 3
2 (3) 1 4 5
3 (1) 1
4 (2) 0 2
5 (1) 2

Output

Code: Select all

5 critical links
0 - 4
1 - 2
1 - 3
2 - 4
2 - 5

Your output is different. http://ideone.com/AuwQb9

[nafeeur_kuet]

Again WA!!

Code: Select all

//Removed after AC.

[lighted]

Your code fails some input below.

Input

Code: Select all

6
4 (2) 1 5
2 (0)
1 (3) 5 4 0
5 (2) 1 4
0 (2) 3 1
3 (1) 0

13
8 (1) 2
3 (1) 1
11 (1) 5
6 (1) 1
2 (3) 12 7 8
4 (2) 10 5
12 (2) 2 10
7 (1) 2
5 (2) 11 4
9 (0)
1 (4) 3 0 6 10
10 (3) 12 4 1
0 (1) 1

23
5 (1) 22
17 (0)
7 (0)
19 (0)
4 (0)
16 (0)
3 (0)
21 (1) 0
8 (0)
12 (0)
22 (1) 5
9 (0)
6 (1) 13
2 (0)
13 (1) 6
15 (0)
18 (0)
0 (1) 21
14 (1) 11
1 (0)
20 (0)
10 (0)
11 (1) 14

24
15 (8) 19 1 18 5 17 0 4 22
22 (7) 12 13 4 15 3 14 6
23 (6) 8 7 19 3 12 20
2 (1) 4
19 (4) 23 20 15 21
8 (2) 23 20
5 (3) 15 12 9
12 (6) 18 23 22 5 7 6
6 (5) 3 13 12 20 22
4 (5) 2 22 18 11 15
10 (1) 11
16 (2) 20 18
14 (3) 20 18 22
9 (3) 5 0 17
0 (3) 9 15 21
11 (2) 4 10
3 (5) 18 6 13 23 22
20 (6) 14 8 16 6 19 23
13 (5) 7 3 22 18 6
18 (7) 15 4 13 12 16 14 3
7 (3) 23 13 12
21 (2) 0 19
1 (1) 15
17 (2) 15 9

29
15 (0)
22 (2) 19 18
28 (3) 1 13 14
11 (0)
5 (1) 14
10 (0)
7 (0)
12 (1) 23
3 (0)
6 (1) 23
8 (0)
26 (0)
16 (0)
1 (2) 23 28
4 (0)
23 (3) 1 6 12
0 (0)
19 (2) 21 22
24 (1) 18
14 (3) 28 5 9
20 (0)
18 (2) 24 22
9 (2) 17 14
25 (0)
2 (1) 21
13 (1) 28
21 (2) 19 2
27 (0)
17 (1) 9

33
25 (8) 18 22 19 32 23 29 12 26
5 (2) 29 27
21 (3) 0 15 7
17 (2) 2 12
20 (5) 24 23 16 6 9
8 (7) 3 18 6 16 27 19 4
31 (4) 14 27 12 28
18 (6) 8 4 10 12 13 25
9 (3) 3 20 10
22 (4) 16 3 25 24
10 (5) 12 0 9 1 18
3 (5) 22 8 9 28 27
15 (2) 21 28
12 (7) 10 6 18 31 17 25 2
26 (5) 0 25 4 23 32
28 (3) 15 31 3
29 (4) 5 25 7 0
11 (0)
19 (4) 8 25 6 0
0 (5) 21 26 10 19 29
7 (3) 29 1 21
2 (2) 17 12
23 (6) 25 13 6 16 20 26
1 (3) 10 13 7
6 (5) 19 20 23 12 8
14 (2) 31 27
16 (5) 22 20 23 8 27
24 (3) 27 20 22
30 (1) 27
13 (3) 1 23 18
27 (8) 16 5 8 31 30 14 3 24
4 (3) 18 8 26
32 (2) 25 26

39
11 (4) 28 16 7 1
37 (5) 26 25 21 24 4
18 (2) 21 22
36 (5) 25 15 19 12 29
21 (3) 18 37 7
3 (1) 0
33 (3) 14 9 15
16 (3) 22 11 14
4 (4) 1 35 37 20
6 (4) 29 13 5 35
35 (4) 4 6 29 5
9 (1) 33
24 (5) 37 5 10 2 13
17 (4) 14 1 23 28
15 (4) 10 33 36 27
29 (5) 7 6 20 35 36
7 (6) 34 23 29 11 25 21
34 (4) 32 7 2 14
2 (5) 20 31 34 24 8
30 (0)
20 (7) 29 0 2 38 12 10 4
38 (1) 20
22 (4) 18 16 19 32
23 (3) 7 17 0
32 (4) 22 34 12 10
8 (4) 2 27 13 31
1 (5) 11 0 4 17 19
25 (3) 36 37 7
0 (4) 1 3 20 23
12 (4) 20 32 36 31
26 (3) 37 31 13
31 (4) 2 8 12 26
19 (4) 10 22 36 1
28 (3) 17 11 14
13 (5) 8 6 24 26 27
10 (6) 15 24 19 20 32 5
5 (4) 35 10 6 24
14 (5) 16 33 28 34 17
27 (3) 13 15 8

46
16 (5) 45 43 8 13 20
42 (1) 23
30 (2) 4 32
7 (2) 18 41
9 (1) 14
45 (2) 0 16
20 (3) 19 18 16
32 (2) 12 30
8 (1) 16
22 (0)
41 (2) 44 7
11 (0)
26 (0)
10 (0)
15 (0)
24 (1) 29
43 (2) 6 16
2 (1) 44
23 (3) 40 42 29
31 (1) 14
5 (0)
13 (2) 36 16
28 (0)
36 (3) 29 17 13
38 (1) 35
4 (3) 30 37 19
27 (0)
3 (3) 29 33 37
0 (2) 25 45
25 (2) 12 0
17 (1) 36
19 (2) 20 4
12 (2) 25 32
40 (1) 23
29 (5) 23 3 36 24 39
35 (2) 38 6
33 (2) 44 3
37 (2) 3 4
21 (0)
39 (2) 29 14
6 (2) 35 43
34 (0)
14 (3) 9 39 31
1 (0)
44 (3) 41 2 33
18 (2) 20 7

48
0 (5) 20 17 45 21 30
25 (1) 18
4 (2) 12 31
20 (2) 0 46
14 (3) 47 8 44
40 (2) 19 47
36 (6) 12 28 46 26 1 29
17 (4) 46 30 0 31
42 (2) 1 24
27 (3) 12 47 34
39 (3) 16 23 8
8 (3) 39 47 14
44 (4) 1 15 14 34
13 (5) 18 16 12 37 22
33 (1) 28
26 (3) 41 19 36
19 (5) 31 12 40 26 23
41 (6) 16 29 26 18 34 37
18 (4) 13 45 25 41
30 (7) 24 45 11 17 0 5 2
21 (4) 37 0 2 35
9 (4) 23 35 12 16
22 (5) 35 12 16 45 13
1 (5) 46 45 44 36 42
16 (6) 9 13 38 39 41 22
7 (3) 46 12 35
12 (9) 6 19 27 36 13 4 22 7 9
15 (2) 32 44
35 (4) 21 22 7 9
3 (2) 45 32
28 (3) 11 33 36
31 (5) 17 6 19 4 10
24 (2) 42 30
10 (2) 47 31
34 (4) 44 29 41 27
45 (7) 30 32 1 0 3 18 22
2 (2) 21 30
37 (3) 21 13 41
32 (3) 15 3 45
5 (1) 30
11 (2) 30 28
43 (1) 46
6 (2) 31 12
29 (3) 41 36 34
38 (1) 16
23 (3) 19 39 9
46 (6) 1 7 36 43 20 17
47 (5) 10 8 27 40 14

49
47 (0)
9 (0)
23 (2) 8 6
3 (1) 39
4 (2) 44 40
5 (1) 14
0 (1) 48
31 (1) 2
8 (3) 23 35 10
20 (2) 42 17
43 (1) 6
11 (2) 40 22
12 (0)
2 (1) 31
32 (3) 14 27 6
35 (2) 29 8
16 (0)
15 (0)
18 (4) 1 34 44 26
29 (3) 19 14 35
13 (0)
38 (3) 39 37 14
28 (1) 33
36 (0)
24 (1) 40
26 (2) 18 17
41 (0)
17 (2) 26 20
33 (1) 28
37 (2) 6 38
7 (0)
27 (1) 32
42 (2) 46 20
1 (3) 40 19 18
34 (1) 18
45 (0)
6 (5) 43 23 37 25 32
46 (1) 42
19 (2) 1 29
21 (0)
40 (4) 24 1 4 11
10 (1) 8
39 (2) 3 38
30 (0)
44 (2) 4 18
22 (1) 11
25 (1) 6
14 (4) 32 5 29 38
48 (1) 0

52
0 (0)
40 (0)
51 (0)
15 (0)
4 (0)
49 (0)
25 (0)
44 (0)
47 (0)
9 (0)
12 (0)
10 (0)
30 (0)
7 (0)
6 (0)
13 (0)
48 (0)
17 (1) 41
34 (0)
33 (0)
20 (0)
22 (0)
11 (0)
23 (0)
43 (0)
1 (0)
50 (0)
24 (0)
16 (0)
29 (0)
46 (0)
14 (0)
5 (0)
36 (0)
21 (0)
19 (0)
32 (0)
37 (0)
38 (0)
2 (0)
39 (0)
3 (0)
31 (0)
27 (0)
35 (0)
18 (0)
26 (0)
28 (0)
42 (0)
45 (0)
8 (0)
41 (1) 17

59
54 (1) 14
21 (1) 12
43 (3) 22 55 47
2 (3) 28 13 49
8 (2) 10 52
5 (2) 15 58
37 (3) 12 30 49
15 (2) 17 5
25 (2) 36 57
9 (1) 46
4 (3) 16 33 47
50 (0)
33 (3) 52 4 39
10 (2) 11 8
42 (3) 35 44 53
0 (0)
16 (1) 4
19 (3) 3 52 48
34 (5) 40 27 36 45 57
51 (2) 29 49
20 (0)
53 (2) 42 24
52 (4) 33 8 6 19
31 (1) 6
24 (4) 44 45 14 53
49 (4) 2 51 37 11
40 (2) 34 6
32 (1) 27
6 (6) 31 40 39 52 11 48
26 (1) 18
11 (3) 6 10 49
18 (2) 47 26
38 (0)
39 (3) 6 13 33
23 (3) 57 58 44
35 (1) 42
36 (3) 25 30 34
27 (2) 34 32
28 (2) 2 13
57 (4) 34 7 25 23
22 (1) 43
41 (0)
12 (2) 37 21
17 (1) 15
58 (3) 3 5 23
29 (1) 51
45 (4) 14 24 3 34
47 (3) 43 18 4
30 (2) 37 36
3 (3) 19 45 58
14 (3) 45 24 54
56 (0)
7 (1) 57
1 (0)
46 (1) 9
55 (1) 43
44 (3) 24 42 23
48 (2) 19 6
13 (3) 28 2 39

Acc Output

Code: Select all

2 critical links
0 - 1
0 - 3

11 critical links
0 - 1
1 - 3
1 - 6
1 - 10
2 - 7
2 - 8
2 - 12
4 - 5
4 - 10
5 - 11
10 - 12

4 critical links
0 - 21
5 - 22
6 - 13
11 - 14

4 critical links
1 - 15
2 - 4
4 - 11
10 - 11

14 critical links
1 - 23
1 - 28
2 - 21
5 - 14
6 - 23
9 - 14
9 - 17
12 - 23
13 - 28
14 - 28
18 - 22
18 - 24
19 - 21
19 - 22

1 critical links
27 - 30

3 critical links
0 - 3
9 - 33
20 - 38

15 critical links
2 - 44
6 - 35
6 - 43
8 - 16
9 - 14
14 - 31
14 - 39
16 - 43
17 - 36
23 - 29
23 - 40
23 - 42
24 - 29
29 - 39
35 - 38

5 critical links
5 - 30
16 - 38
18 - 25
28 - 33
43 - 46

21 critical links
0 - 48
1 - 19
2 - 31
3 - 39
5 - 14
6 - 25
6 - 43
8 - 10
11 - 22
11 - 40
17 - 20
17 - 26
18 - 26
18 - 34
19 - 29
20 - 42
24 - 40
27 - 32
28 - 33
38 - 39
42 - 46

1 critical links
17 - 41

22 critical links
4 - 16
4 - 33
4 - 47
5 - 15
5 - 58
6 - 31
7 - 57
9 - 46
12 - 21
12 - 37
14 - 54
15 - 17
18 - 26
18 - 47
22 - 43
27 - 32
27 - 34
29 - 51
35 - 42
43 - 47
43 - 55
49 - 51

Don't forget to remove your code after getting accepted.

[lusho]

//someone help me please pleaseeeeeeee
// i am getting WA and prove all the test cases and the output is correct in this post but UVa gives me a WA
// somebody could tell me pleaseeeee

Code: Select all

#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define SZ 100
bool M[SZ][SZ];
int N,colour[SZ],dfsNum[SZ],num,pos[SZ],leastAncestor[SZ],parent[SZ];
void dfs(int u){
int v;
stack<int> S;
S.push(u);
while(!S.empty()){
v=S.top();
if(colour[v]==0){
colour[v]=1;
dfsNum[v]=num++;
leastAncestor[v]=num;
}
for(;pos[v]<N;pos[v]++){
if(M[v][pos[v]] && pos[v]!=parent[v]){
if(colour[pos[v]]==0){
parent[pos[v]]=v;
S.push(pos[v]);
break;
}else leastAncestor[v]<?=dfsNum[pos[v]];
}
}
if(pos[v]==N){
colour[v]=2;
S.pop();
if(v!=u) leastAncestor[parent[v]]<?=leastAncestor[v];
}
}
}
struct edge{
int u,v;
edge(){
}
edge(const int _u, const int _v){
u=min(_u,_v);
v=max(_u,_v);
}
bool operator < (const edge &X) const{
if(u!=X.u) return u<X.u;
return v<X.v;
}
};
vector<edge> v;
void Bridge_detection(){
memset(colour,0,sizeof(colour));
memset(pos,0,sizeof(pos));
memset(parent,-1,sizeof(parent));
num=0;
int ans=0;
for(int i=0;i<N;i++) if(colour[i]==0) dfs(i);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(parent[j]==i && leastAncestor[j]>dfsNum[i]) ans++;
printf("%d critical links\n",ans);
v.clear();
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
if(parent[j]==i && leastAncestor[j]>dfsNum[i]) v.push_back(edge(i,j));
sort(v.rbegin(),v.rend());
for(int i=v.size()-1;i>=0;i--) printf("%d - %d\n",v[i].u,v[i].v);
printf("\n");
}
int main(){
int u,v,e;
char c;
while(scanf("%d\n",&N)==1){
memset(M,false,sizeof(M));
for(int i=0;i<N;i++){
scanf("%d",&u);
scanf("%c%c%d%c",&c,&c,&e,&c);
for(int j=0;j<e;j++){
scanf(" %d",&v);
M[u][v]=M[v][u]=true;
}
}
Bridge_detection();
}
return 0;
}

[brianfry713]

That code won't compile, use min() instead of <?=