
315 - Network
Moderator: Board moderators
-
- Learning poster
- Posts: 98
- Joined: Fri Aug 17, 2012 9:23 pm
- Location: Dhaka
- Contact:
Re: 315 Network
Even toolkit gives wrong output for this problem.... 

Re: 315 Network
Getting WA....plzz help
Code: Select all
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<deque>
#include<queue>
#include<map>
#include<sstream>
using namespace std;
typedef long long int L;
typedef unsigned long long int U;
int n;
vector<int>v[110];
int dis[110];
int back[110];
int p[110];
int visit[110];
bool arti[110];
int k;
int c;
int r = 0;
void dfs(int x)
{
visit[x] = 1;
dis[x] = k++;
for(int i = 0;i<v[x].size();i++)
{
if(!visit[v[x][i]])
{
if(x == 1)
r++;
p[v[x][i]] = x;
dfs(v[x][i]);
}
}
}
void art(int x)
{
back[x] = dis[x];
for(int i = 0;i<v[x].size();i++)
{
if(back[v[x][i]] > dis[x])
{
art(v[x][i]);
if(back[x] <= back[v[x][i]])
{
arti[x] = 1;
}
back[x] = min(back[x], back[v[x][i]]);
}
else
{
if(p[x] != v[x][i])
back[x] = min(back[x], dis[v[x][i]]);
}
}
}
main()
{
while(1)
{
scanf("%d", &n);
if(!n)
break;
for(int i = 0;i<=n;i++)
{
v[i].clear();
visit[i] = 0;
arti[i] = 0;
p[i] = -1;
}
string str;
getline(cin, str);
while(1)
{
getline(cin, str);
stringstream ss(str);
int x;
ss>>x;
if(!x)
break;
int y;
while(ss>>y)
{
v[x].push_back(y);
v[y].push_back(x);
}
}
r = 0;
k = 1;
dfs(1);
for(int i = 0;i<=n;i++)
{
visit[i] = 0;
back[i] = dis[i];
}
c = 0;
art(1);
for(int i = 1;i<=n;i++)
{
if(arti[i])
c++;
}
if(r == 1)
c--;
cout<<c<<endl;
}
}
-@ce
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 315 Network
brianfry713 wrote:Try running dfs N times, once with each node turned off.
Check input and AC output for thousands of problems on uDebug!
Re: 315 Network
@brianfry713...i got AC using brute force as u said.
But whys is the above algorithm not working...any help with that?brianfry713 wrote:Try running dfs N times, once with each node turned off.
-@ce
Re: 315 Network
Whats problem in my code, i got wa, help anyone.
I just get the graph then find out the articulation point, if my algorithm is ok then for which input my code failed else whats the algorithm of this problem.
My code
I just get the graph then find out the articulation point, if my algorithm is ok then for which input my code failed else whats the algorithm of this problem.
My code
Code: Select all
//Templet start
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
#include <string>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <algorithm>
using namespace std;
#define sf scanf
#define pf printf
#define long long lld
#define llu unsigned long long
#define fo(i, n) for(i = 0; i < n; i++)
#define of(i, n) for(i = n - 1; i >= 0; i--)
#define mem(n, v) memset(n, v, sizeof( n ))
#define eps 1e-8
#define INF 5000
#define pb push_back
#define maxn 200000+2
#define white 0
#define black 1
typedef vector <int> vi;
typedef vector<vi> vii;
void DFS(int u);
void reset(int n);
vector <int> graph[ 102 ];
int node, edge, k;
int dfs_num[ 102 ], dfs_low[ 102 ], dfsNum, par[ 102 ], articulation_point;
bool ap[ 102 ], vis[ 102 ];
char print[ 102 ][ 32 ];
//Templet end
void input();
int main()
{
//freopen("output.txt", "w", stdout);
input();
return 0;
}
void input()
{
int n, i, u, v;
char ch[ 6 ], garbag;
bool ck;
while(sf("%d", &n) && n)
{
reset(n);
//Get input ************************
for(i = 0; i < n; i++)
{
ck = true;
while( true )
{
sf("%s", ch);
garbag = getchar();
if(ch[ 0 ] == '0') break;
if( ck ) u = atoi( ch ), ck = false;
else
{
v = atoi( ch );
graph[ u ].push_back( v );
graph[ v ].push_back( u );
}
if(garbag == '\n') break;
}
if(ch[ 0 ] == '0') i = n;
}
//********************************
for(k = 1; k <= n; k++)
{
if(!vis[ k ]) DFS( k );
dfsNum = 1;
for(int i = 1; i <= n; i++)
{
dfs_num[ i ] = dfs_low[ i ] = 0;
par[ i ] = -1;
}
}
// Print result *******************
printf("%d\n", articulation_point);
//*********************
}
}
void DFS(int u)
{
dfs_low[ u ] = dfs_num[ u ] = dfsNum++;
vis[ u ] = true;
for(int i = 0; i < graph[ u ].size(); i++)
{
int v = graph[ u ][ i ];
if(dfs_num[ v ] == 0)
{
par[ v ] = u;
DFS( v );
dfs_low[ u ] = min(dfs_low[ u ], dfs_low[ v ]);
if(dfs_num[ u ] == 1 && dfs_num[ v ] > 2 && !ap[ u ])
{
articulation_point++;
ap[ u ] = true;
}
if(dfs_num[ u ] != 1 && dfs_num[ u ] <= dfs_low[ v ] && !ap[ u ])
{
articulation_point++;
ap[ u ] = true;
}
}
else if(par[ u ] != v) dfs_low[ u ] = min(dfs_low[ u ], dfs_num[ v ]);
}
}
void reset(int n)
{
dfsNum = 1;
articulation_point = 0;
for(int i = 1; i <= n; i++)
{
vis[ i ] = ap[ i ] = false;
graph[ i ].clear();
dfs_num[ i ] = dfs_low[ i ] = 0;
par[ i ] = -1;
}
}
Code: Select all
enjoying life .....
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 315 Network
Try running dfs N times, once with each node turned off.
Check input and AC output for thousands of problems on uDebug!
Re: 315 Network
Just got AC. There are no disconnected graphs in the input as the problem statement says.
Turn off and DFS approach works, however I used Tarjan's algorithm starting from node 0 for each case (which would have failed for inputs such as 5 0 0).From each place it is possible to reach through lines every other place, however it need not be a direct connection, it can go through several exchanges.
Re: 315 Network
Is that the only way of solving this problem? I am using tarjan's algorithm(iterative). but keep getting WA.brianfry713 wrote:Try running dfs N times, once with each node turned off.

Even after I have handled the 5 0 0 case.
Code: Select all
AC
Last edited by moxlotus on Fri Sep 27, 2013 8:16 am, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 315 Network
Yes this problem can be solved using a simple and easy to code DFS or a correct implementation of Tarjan's algorithm.
Check input and AC output for thousands of problems on uDebug!
Re: 315 Network
BrianFry, thanks for the reply. found where my bug is.
Bug: my IO could not handle the trailing space behind each line.

Bug: my IO could not handle the trailing space behind each line.
brianfry713 wrote:Yes this problem can be solved using a simple and easy to code DFS or a correct implementation of Tarjan's algorithm.
Re: 315: Network
Hey replying roticv, the post almost 10 years ago. In your posted code, the articulation test for root node might be wrong. We are not looking for "if the #no of connections from root node is more than 2". We are looking for if the # of children for root node from the resulting DFS is more than 2.
Also, the test cases might re-iterate one pair of connection more than once.
like:
It is a pitfall for those who want to implement the graph using adjacency list. The test for number of children at root node might fail. We might find multiple children for root node that are pointing to identical nodes in the graph. Just a reminder for people who wasted a lot of time on this problem like me.
Also, the test cases might re-iterate one pair of connection more than once.
like:
Code: Select all
2
1 2 2 2
2 1
0
0
Re: 315: Network
The following test case is wrong because in the problem statement it says that each block ends with a 0 and the entire input itself ends with a 0. So we are missing a zero here.
Invalid Input
It should be
Invalid Input
Code: Select all
1
0
Code: Select all
1
0
0
Re: 315 - Network
I'm working on this task since yesterday and still don't know what's wrong in my code
Code: Select all
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
using namespace std;
struct node{
vector< int > edge;
int low;
int d;
bool art;
};
node graph[105];
int n,t, result;
int DFS(int v, int p)
{
graph[v].d=t++;
graph[v].low=t-1;
for(int j=0;j<graph[v].edge.size();++j)
{
if(graph[v].edge[j]!=p)
{
if(graph[graph[v].edge[j]].d==-1)
{
DFS(graph[v].edge[j], v);
graph[v].low=min(graph[v].low, graph[graph[v].edge[j]].low);
}
else
graph[v].low=min(graph[v].low, graph[graph[v].edge[j]].d);
if(graph[v].d<=graph[graph[v].edge[j]].low)
graph[v].art=true;
}
}
}
int main(int argc, char const *argv[])
{
ios_base::sync_with_stdio(0);
cin>>n;
string line;
while(n!=0)
{
cin.get();
result=0;
for (int i = 0; i < n; ++i)
{
graph[i].edge.clear();
graph[i].d=-1;
graph[i].art=false;
graph[i].low=110;
}
int a, b;
while(getline(cin,line))
{
istringstream ss(line);
ss>>a;
a--;
if(a==-1)
break;
while(ss>>b)
{
b--;
graph[b].edge.push_back(a);
graph[a].edge.push_back(b);
}
}
t=0;
for(int i=0;i<n;++i)
{
if(graph[i].d==-1)
{
int c=0;
graph[i].d=t++;
graph[i].low=t-1;
for(int j=0;j<graph[i].edge.size();++j)
{
if(graph[graph[i].edge[j]].d==-1)
{
DFS(graph[i].edge[j], i);
++c;
graph[i].low=min(graph[i].low, graph[graph[i].edge[j]].low);
}
}
if(c>1)
{
graph[i].art=true;
}
}
}
for (int i = 0; i < n; ++i)
{
if(graph[i].art)
result++;
}
cout<<result<<"\n";
cin>>n;
}
return 0;
}
Re: 315 - Network
Input
Acc Output
Code: Select all
2
1 2
0
5
5 1 2 3 4
0
5
5 3
2 1
4 3
3 4
1 3
0
6
2 1 3
5 4 6 2
0
11
7 9
1 11
4 1
5 11
8 3
3 7
9 3
6 10
10 11 3
2 7
0
12
11 6
12 5 11
8 4
1 5
2 5
7 1 11
6 10
10 3
9 11
5 1
4 5
0
13
3 10
1 2 13
6 9 5 4
7 9
2 6
5 9
10 11
9 3
8 6
11 4
12 2
0
14
2 14
4 9
11 5
3 10 1
7 3 8 4
14 1
13 1
1 10
6 12
10 3
8 2
12 4 6
5 14
0
15
14 5
5 3
9 2
4 2 3
1 15 3
15 10
3 12 5
2 8
11 15
12 4 13 15
8 5
13 11
6 4
7 4
0
16
2 6
3 15
11 4
7 16
16 8
8 3
1 7
14 11
9 6
4 10 7 13
10 6 9 16
12 14
6 7
5 13
0
16
15 14
5 7
14 6
3 1
1 9
7 16
4 6
10 3
6 14
12 5
2 4
9 7
13 7
8 14
11 8
16 2
0
17
17 7
2 14
13 16
14 15
7 4
11 9 5 15
9 17
4 15
15 4
12 3 10
5 14
10 9
6 10 12
8 11
16 5 6
1 16
0
19
9 17
16 9
5 7 9 4 18 3 19
18 2
15 19
4 2
19 10
12 6
1 19
14 8
6 11
2 16
10 5
8 3
13 19
17 7
11 7
0
21
17 4 18
1 11
7 5
13 1
3 1
14 5
15 20
9 12
6 8
16 14
18 8
8 4
20 18 10
2 3
12 5
5 9 20
19 20 9 11 2
11 3
4 15
10 3
21 3
0
22
4 19
6 11
18 20
19 3
22 8
15 2
11 22
3 2
2 6
5 18
21 14
12 21
1 3
20 1
16 10
8 4
9 10 13
17 10
14 19
10 6
13 3
7 6
0
22
16 19
6 18
1 18
9 19 21 6 16 22 10
3 14
8 7
10 9
2 11
4 10
15 6
19 18
12 15
21 1
7 9 11
5 22
22 17
20 15
14 8
13 15
0
24
15 5
24 2 1
13 7
6 14 17
12 17
16 3
23 2 3 24
11 5
3 8
17 10
9 14
18 22
4 1
10 3
5 19 16 18
14 4
21 6
1 4
7 2
19 24
20 6
0
26
19 8
22 23
5 17
25 21
23 11
20 25
4 6
14 3
6 25
15 24
1 10
12 24
21 23
13 5
10 11
26 16
8 13 10 21
9 5 1 12
18 26
17 13
24 13 9
11 12
2 14
7 23 9 17
3 9
16 24
0
26
21 15
26 16
16 23
24 5 15 26
4 11 16 23
7 24
19 4
23 21 15
17 1
14 11
18 17 7
11 6
3 19
10 17
8 5
12 26
2 3
22 7
6 23
20 4 21
13 16
1 24
25 26
9 23
0
28
7 18
15 19
17 1
16 17
11 2
10 11 12
6 5
27 16
26 25 20
23 4
4 2
9 5
3 5
2 17 28
13 12
24 7
20 8 22
19 25
8 23
5 9 25 26 8 3
1 25
12 7
18 27
28 22 26
25 7
14 6
22 6 10 18
21 1 23
0
29
3 2
19 4
10 25
14 17
1 23
15 23
16 3
4 22
25 13 6
28 16 1
7 24
8 7
23 24 20
13 3
21 28
6 26
2 14
29 6
18 7
24 15
26 20 7
9 21
22 5
27 17 29
20 27
17 15
12 27
11 17 13
5 22 3 20
0
32
28 19
30 12
29 31 17
24 18
2 30 15 23 7
22 31
25 29
14 7
7 6
31 7
1 31
15 13
19 30 4 27 28
21 24
10 5 13
18 15
17 26 28
4 19 10
23 2
8 25 26
11 25
6 27 17
32 15 2
26 15 27
3 21
13 22
27 4 24 10 28 25 19 30
9 17
5 32 25
12 13
16 8
20 4
0
36
20 19
12 21 11 16 7 14 19 29 35 8
33 8 3
11 10
1 11 25 31
19 20
29 24
13 26
14 29
10 12
16 18 9
5 23
25 4
30 19
36 30
22 11 14
26 11
2 14
32 23
21 12
3 33
34 22 19
7 33
28 19
6 26
24 4
17 1
31 32 25 8 19 15
9 3 33
15 8
35 2
27 11
0
37
6 25
33 34
19 22 12
15 20
32 33
37 7 9
4 36
31 21
35 8
25 28 26
29 35
7 1
20 21
23 15
17 19 23 32 34 21 6 5
18 8 25 33 5
21 1
27 5
16 6
11 27
36 1
22 10
14 37
26 11
12 23
24 13
9 3
28 25
3 7
5 22
30 7
1 9
13 12 25 24
34 7
8 36
2 29
0
38
2 3
18 4
3 14
17 8
35 21
12 26
6 7
11 19
13 7
1 10
22 11
7 11
10 3 31 32
36 15 34
5 4 27 18
14 12 31
38 8 37
15 4
34 26
9 27
33 23
31 18
19 11
4 18 33
16 22 5
27 24
28 33
20 22 11 14 2
30 37
8 12
25 27
21 3
26 16
29 35
0
45
11 28
43 32
8 18
14 23 20
22 34
18 43
33 31
20 16 31 4 29 3 35 40 36 15 33 45 6 23 10 17 32 18 24 27
5 8
44 39
29 26
25 44 13
38 18 26
7 30 32
27 34
19 44
23 31 11
24 8
39 21 16 40 1
21 38
40 11
1 5 28 44 29 10
10 23
17 5 6 24
13 36 16 12
4 32
2 27 33 4 13 30 24 11 31
37 9 1
42 8 14 36 7 40 30 17 2 31 6 34 29 4
28 25
45 6
35 22
31 4
34 2
41 22
0
46
1 9
14 40
11 8
46 34
20 18
30 41 21 5 34
38 29
36 4 35 26
6 45
34 40
19 13 33
29 35
17 43
4 23
10 7
2 43 35
25 4
13 38 7
24 23 19 14
18 1
8 3
42 11
16 27
35 46
43 33
21 17 46 1
26 31
23 3
33 29
40 19
9 16 32 35 34
3 26
28 35
27 35
44 8 13
45 41 26
41 21
5 4
37 16
15 12
12 32
7 12
39 34 5 21 11
22 33 14 21
0
46
44 37
13 11 23 24 5 25 10 14 31 20 16 15
33 40
45 12 37
31 37 23 7 22 42 16 36 39
10 8 28
5 39
1 17 4
39 41
17 30
18 11 45 29 28 2 20 37
32 19
8 24
2 7
46 30
28 2
43 8 26
23 20
40 7
20 29
21 9
34 10
11 26
41 23 25 16 28
12 23
26 29
24 32
27 26 29 16 43 5 41
3 45
15 40 43 41 1 38 17
19 35 34 37 30 32 16 29
35 20
7 22
22 2
25 42 2 31 43 27
6 11 20 45 29 30 39 43 8 33
38 27
37 12
4 35 45
36 38
42 18
29 17
16 17 11 15 41 6
9 15
0
48
9 14
17 47
1 44 19
21 48
13 5 27 12 17
6 31
35 6 46 40
26 43
11 38 3
23 19
2 8
43 35
41 33
42 13
12 20 19 18 41 22
37 10
47 39 28
14 31
4 32
44 23 22
3 37
15 42 25 6
7 9
29 27
40 29
5 17
39 38
34 43 42
25 13 16 33 2 1 29
8 26
48 24
27 46
36 26
16 17
33 44 2 43 19
10 35
38 6
18 33 14
20 7 24
45 35 18 4
19 7
30 37 16
0
51
14 6 37 3 44 28 49 12
47 43
29 13
18 51 10
2 6
32 21 34 22 28
9 2
26 14 24 8
33 24 37 17
31 36
28 5
6 31
38 37 19
15 24 41
30 45
8 43
22 46
36 49
41 43
1 8
46 15 13
35 32
13 50
4 21
39 40
5 16
34 10 14 21
10 41
45 6 24 25 7
42 39 33 28 40 11
50 51
17 34
43 48
7 43 51
24 14
49 28
16 11
48 12 32
25 22
3 12
19 31
20 22
37 18 32
12 28 41
40 18 41
51 43
44 9 46 17 43
21 49
23 38
11 18
27 40
0
22
11 15
5 17
10 12
8 18
22 12 6
20 22
15 18
1 14
3 2
13 2
7 16
16 10
4 9
19 17
12 17
6 9
18 6
17 1
21 2 20 8
0
38
22 29 26 23
13 4
21 30 25 34
12 30
6 2
10 9
30 32
1 2 27 21 8
23 22 37 11
24 26
37 11
33 26
11 21
38 29 10
14 25
34 4
7 15
2 32
3 36
29 8
16 10 29
36 29
9 21
8 20
17 19
5 26
4 12 13 19
28 16
18 35
31 30
20 15
35 27
0
39
2 22 28
22 2
30 24
14 19
13 17 25
8 10
29 24
26 17
17 6
6 21
21 26
34 39
18 5 30 32 21 11 3 25 7 33 28 14 23 19 4 31 2 1 29 13 8 12 38 20 10 39 36 22 35
24 20
38 9 31
3 18
10 14
27 16 7 22 24
37 38
31 30
4 22 14
1 12
19 31
9 32
15 4
0
7
2 7
4 7
7 4
6 3
5 4
3 7
1 3
0
13
10 1
7 11 4
4 13
9 1
12 13
13 9 3
11 13 2 6
3 7
5 12
8 6
0
18
6 2
8 6
5 9
9 16
2 15 18
7 4 1
4 7
10 4
17 10
3 13
16 15
13 1
18 17
11 13
15 9
12 1
14 10
0
24
12 15
6 7
2 3
1 2
21 8
3 21
22 5
20 7
13 8
4 23
10 16
19 16
17 11
14 3
24 2
15 3
23 2
7 6
18 7 22
8 18
5 20
11 5
9 11
16 14 11 13 7 15 9 23
0
30
3 1
4 28
11 14
22 18
30 4
24 16
27 14
9 19 26
21 24 22 25
18 30
2 16
6 26 3
29 20
5 23
12 20 14 4 7 21 29
1 24
16 12
8 3 27
17 21
15 27
25 13
28 2
13 2
19 7
7 18
14 27
10 21
23 19 11
0
51
51 12
37 27
10 44 41 35 28 42
32 35 28 24 20 38 3
2 29
45 42 37 46
22 41
40 17
1 6 7
28 40
20 15 45 26 41 10
26 3
44 22
31 44
14 22
35 11
17 12 44 51
6 43 13 18
47 24 23
41 2
38 14 44
8 17
25 20
50 34
24 33 5
43 11
5 11
27 47 16 12
18 22
34 22
7 46 38 23 36 4 39 42 21
33 32
12 35
19 13
39 42
9 34 37 32 16 27 14
48 7
3 38
23 47
4 22
13 1 11 7
42 28
46 48
49 40
36 22 15
21 43
30 17 28 44 3
0
17
17 10
13 12
3 8
7 11
15 10
16 2
12 7
6 16
2 12
9 10
1 15
5 3
8 13
14 9
4 8
11 3
10 16
0
14
12 5
14 7 2 3 4
11 5
5 6
2 10
6 10
9 14
3 2
4 7
10 5
1 5
7 6
13 3
8 13
0
20
7 9
6 13
5 16
14 7
15 7
11 16
19 20
13 7
2 11
1 3 18
16 18
12 20 14
18 8
9 14 4
8 7
4 7
10 8
3 7
20 4 3 17
0
40
28 19
39 20 7
32 11
21 34
24 13
19 14 1
9 16
27 33
8 36
38 33
16 23
3 17 8
7 39
29 15
17 27
10 39
11 2
5 10
30 28
35 12 3
25 29
40 31 7
18 10
4 25
13 11
34 20
31 36 33 20 11
12 25
6 7
22 32
23 10 24
20 26 29 16 9 34
33 4
36 5
26 6
15 8
1 23
37 36
0
12
11 2
9 3
7 1 10
5 2
10 8 12
12 2
8 11
4 2
3 10
6 5
0
49
46 22
39 36 24
16 22 14
28 9
31 16
15 31
10 30 31 45 26 42 35
42 44 35
38 12
19 16
7 19 27
23 39
4 35
37 44
25 8 17
48 22
33 25 45 49 42
49 48
13 8 24
47 29
22 25 19 4
29 36 14 40 33 15
35 15 1
11 1
27 5
12 18
41 49
6 17
36 27
3 8
8 49
18 37
24 19 44
14 43
1 18
34 11
17 40
40 39
9 36 37
20 30
5 31
44 43
32 46 6 43
45 28
26 4 38 44 29 6 10
30 21
21 37
2 12 45 17
0
17
14 2
16 15
13 15 6 11
6 9
5 1
2 4
1 4
15 1
11 4
8 5
7 14
4 10
3 11
10 5
9 1
17 9
12 14 15
0
51
20 40
33 25
46 28
7 35
2 15
18 34
12 33
42 40
41 38
15 25
45 2
31 14
1 9
14 39
39 17 14 9 41 16 47 29 42 18
21 18
11 28 6 1 2
17 19
22 6 31
19 11
50 48
4 29
27 29
36 51
28 24
29 34
48 34
9 21 45 39 12 43
8 30
26 50 3 7
49 21
6 13 29 17
37 8
5 51 48 1 26
40 47
13 15
32 8
44 38
24 33
35 50 43
47 41
43 13 44 51 45
16 5 37
51 27
10 8
25 48
23 44 37
0
48
5 38
8 2
12 5
47 38 46 11
14 46
30 18
26 22
1 4
27 38
10 31
38 19
13 20
43 25
35 45 24
46 48 41 34 3 28 44 13 10
4 7 48 15 17 43 29 40 8 16 31 47
23 14
11 29
48 18
20 38
25 12
6 14 36
36 38
3 20
41 19
21 44
19 20
22 7 19 40 29 33 18
9 22
34 27 15 28 3 41 46
17 11
44 16
24 16
18 48
29 8
37 9
2 16
28 48
15 26
39 46
31 36
16 18
32 28
33 31
7 36
40 11 19
45 28
42 27
0
17
9 5
2 12
16 6
7 2
14 17 5
11 10 9 16
13 1
4 15
17 7
8 10
1 5
5 7
10 16
15 10
12 6
6 17
3 11
0
29
28 25
19 1
12 18
16 29
27 8 3 11
22 17
26 2
14 2
15 14
10 25
8 5 25 24
24 25 3
2 24 15 16
7 1
29 2
21 6
6 1
17 11
3 16
4 2
9 16
23 4
11 8
1 14
13 15
20 29
18 14
0
42
32 22 42
22 1 11 20
20 38
8 23
28 31
26 42 34 18
9 38
4 14
34 11
11 24
18 22
12 39
41 28
33 7
16 37
7 31
24 9 17 42
2 20
38 30 29
35 27
27 30
36 13
39 21 26
17 40 42
29 16 2 31
13 8 25
21 5
5 36
31 5
25 22
10 19 40
15 28
3 19
23 9
30 5
1 14 7
6 20
0
28
10 1
11 20
21 24
7 27 9
15 6
18 9 23
23 18 21 9
4 1
14 6
5 2
25 21
6 17
22 24
17 3
3 15
26 13 18 9
24 17
1 5
2 7
20 14
8 13 15 20
19 4
13 23
28 15
9 23
12 8
16 28 15 8
0
13
7 4
10 7 1
2 12
4 7
6 13
8 11
13 11 1
1 12
9 1
11 9
3 10
5 3
0
35
23 30
7 23
19 11
24 29 34
8 3
15 35 20
33 10
12 1
35 19
11 4
32 35
34 31
3 16
20 19 2
27 13
26 17 30
21 20
10 9
30 27 31 21 16 1
1 19
5 34 13
4 15
16 8 24 19 35 2 30
31 11
22 31
9 2
18 12
14 6
2 29
25 2
13 25
6 13 23 27 19 4
29 11
17 1
28 30 7
0
12
1 4
4 12
2 8
7 2
9 12
12 1
5 8 11
6 12
3 9
8 9 6
11 1 2
10 9
0
4
3 1
1 2
4 2
0
10
4 1
5 4 10 8
8 6
7 8
9 3
1 5
2 7
3 8
0
50
34 5
46 9
11 1
12 13
13 32
17 48
14 12
22 2
2 5
20 44 35 11
39 10
47 17
15 27
35 49
3 20
42 11
8 24
21 37
16 36 17
6 37
33 11
1 19
19 40
7 49 21
26 3
10 25
36 5
43 31 10
25 48
9 33 2
18 25 50 20 5 11 37 26 36 35 21 48 15 8 1 39 2
50 5
5 18 9 1 42 43 24 11
44 17
28 1
37 17
30 5 21
4 24
27 5
48 1 17 2 22
49 39
32 16 48 40 2 14 3
31 2 32
29 25
45 3
40 43 38
41 22
24 28
23 5
0
10
7 3
6 7
10 7
5 1
1 3
2 10 8
8 9
4 5 7
0
17
13 3 8 15
17 15
5 3
3 11
7 10
1 6
9 8 2
15 16
2 7 3
6 8
14 3 10 11 13
11 13
4 17 5
10 2
16 4 10
12 7 8 16 10
0
47
25 16
47 39 11 14 16
46 15 2 7 5
23 41
10 17
41 45
19 22
21 20
37 28
40 38
32 33
24 13
7 4
15 14
2 22
5 8
43 17
45 42 38 47
38 21 18 45
13 33
28 44
26 29 28
44 32 23
35 45 12 16 29 30 13 8 38 14 36 11 25 17
17 23
14 44
31 19 32
11 3
6 16
16 7
1 29
39 12
29 33
36 44
20 39
8 15 9 47
34 41 23 16
22 32
3 37 11
9 40
33 15 37 7
30 3
18 17
42 33 22 35
4 18
12 2 43
27 30
0
23
7 6
14 18
22 5 21
5 19
23 15
10 4
13 9
17 14 2
12 7
4 1
9 15 21 17
18 11
15 7
21 7
16 3
8 18
6 7
11 2
20 1
19 7
3 9
2 1
0
8
6 5
7 5
8 4
4 2
3 8
2 6
1 7
0
35
27 3
21 16
10 33 11 20 23 30
33 6
28 31
35 9
32 28
18 35
6 8 31
24 20 31
4 19
23 16 18
8 2
11 33
29 2
19 33
25 27
26 6 33 29
3 17
13 6
30 17 33 6
15 22 35 21 3
20 17
22 4
34 5 6 8 9 3 4 29 32 31 15 12
31 14
5 9
16 31
1 23
17 19
14 9
2 4
9 8
7 34
0
7
6 3
4 3
5 2
2 1
7 2
3 4
1 6
0
48
32 9
48 3
8 9
19 43
6 15
28 39 10
47 25
42 47
9 3 14
27 25
25 31
16 33 37
34 41
7 42
26 45
18 25
36 44
17 34
12 2
13 19
41 32
20 6
14 4
15 8
45 21 22 9
23 33 21 12
4 13
38 33 12 41
22 7 35 17 9 41
1 15
11 3 2 40
31 25
37 13 8
40 30
43 34 19
21 10 45 36 43
29 36 8 24 6
44 9 1
30 23 10
3 46
33 32
2 37 41 1
24 38 34
35 21 19 6 13
46 12 26
39 41
10 25
5 20 46
0
9
4 7
2 6
8 3
1 2
7 1
6 3 4
3 1
5 2
9 3
0
10
8 1
9 4
1 2
3 2
6 8
5 7
7 10
10 7
2 9
4 5
0
45
29 34
23 14
38 27 18 44 3 16
40 25
42 6
30 42
16 11
33 25 44 6 40
35 25
9 27 38
39 14
3 1 40
26 6
41 16 33 19 43
10 19 2 29 42 6 4 16 24
28 36
24 37
15 26
17 24
2 6 23 25
21 31
43 28
36 38
13 15
12 26
34 26 1
7 9
11 1
22 1
19 28
8 15
1 34
31 10
14 24
32 19
27 45
20 17
6 7 27 15
45 39
25 10
4 41
37 35
5 3
0
13
7 10 12
5 13
13 3 7
8 5
9 6
3 9
2 7
6 9
1 4
12 4
4 8
10 9
11 7
0
83
16 62 57 31 37 77
57 41 59 49 63 62 67 80 65
53 13 47
3 77 70
7 59 62
51 77
31 42
14 29
9 62
60 34
37 3 61 74 10 53
56 71 30
72 33
77 71
68 29
21 83
45 1
41 36 51
8 66 1 15 80
79 20
83 30
82 14 49 23
64 29
61 63
19 62
75 69
78 70
33 48
73 12 47
58 75 45 33
70 3 65 74 36 32
42 15
6 51
38 12
25 26 70
18 38 55 26 8 13 76 47
67 72
80 21 43 55 53
69 82
20 36
48 52
43 13 38 41 17 68
47 73 71 16
44 6
1 53
46 33 41 68
32 51
49 30 65 24
76 55
15 40
81 42 5 34 14
71 83
55 39
34 80 19
11 24
74 29
59 46
23 7
28 77 38 75
4 42 46 18 83 64 16 80 30 31 41 50 22 20 77 62 21 81 79 65
40 74
30 48
54 2 68 42 81 26
62 13
22 76
65 38
35 21 2 20
24 41
50 60
66 25
2 29
63 70 21 46 26 9
13 74 33 8
29 59
52 6 40
26 45 16 33 6 64 35 74 51 3 53 77 24 36 80 11 31 9
27 1
0
13
3 5 10
2 11
9 11 7 8
7 5
8 3
5 7
4 7
11 9 1
1 11
13 8
6 9
12 4
0
44
39 43
28 9
16 40
24 22
15 22
34 44
37 19
40 34 1
21 13
38 34
29 15
27 29 8
41 30
8 13
1 8
32 39
14 19
26 30 10
31 39
36 3 7
42 23
23 30 13
12 13 44 19 8 17 39 41 4 32
2 5
30 31
7 39
11 2
20 5
13 21 12 23 25
3 42
19 3
9 21 23
10 8 21 39 34 41 11 43
33 14
5 22
6 33
25 31
43 30
18 3
35 34
0
34
17 23 33 30
22 18 33
34 7
6 1
31 1
32 27
8 1
13 28
9 4
2 32 7
18 25 31
5 27
11 30
16 1 34 29
33 3
12 11 16
14 15
24 7
1 17
4 33
7 5
28 22 11 8
29 12
19 8
10 24
27 20
30 11 10 3
15 22 30 31
23 30
26 8
20 10
25 9
3 20 24
21 22
0
34
15 30
23 27
13 26
7 23
3 4
18 19
17 30
4 5
20 30
25 7
12 3
22 23
33 17 1
28 7
21 3
2 8
19 23
1 22
30 8
24 19
6 27
31 10
8 11
5 1
9 7
26 9
34 12 8 32 20 24 1 9 26
16 8
32 26
27 15 18 19
29 3
10 23
14 27 9
0
3
1 3
3 1
2 1
0
48
6 16
32 15
15 21 13
41 24
18 40 5 19 1
5 42
44 39
25 23
47 2 20
36 18
34 1
11 33
16 34
22 29
43 3
48 30 33
10 37
13 25 17
17 29 22
30 34 21 48 33
1 42
29 18
24 1
31 45
12 20
21 41
9 30
40 45 29
37 42
33 43 2 18
45 5 11 28 13 20
39 11 10
19 38 2
3 47 7
42 32 27
4 22
38 31
8 2 33 42
27 3
35 11
28 2
2 43
20 34 7
46 18 17 5 11 42 47
14 29
23 37
26 38
0
39
24 33
3 16 21 11 27 10 7 33 8
2 3
16 34 11 10 33 27
11 20
12 24 19
19 38
22 9
5 27
23 20
39 33
14 29 6
31 26
15 26
35 17 36 1 16
36 1
25 27
6 21
13 37 4
17 12
34 20
30 25
20 16
8 27
33 34
28 26
32 12
26 27 24 38 21 12 39
29 9
1 34
18 36 2 8 20
27 29
21 23 5 7 11 12
38 10
37 38
0
30
20 17
27 12 6 9
3 28
19 1
2 21 23
9 6
15 7 11 3 20 27
25 28
18 8
28 8 6
10 5
22 10
29 20 9 7
21 16 6
30 9
7 15
6 21 11
12 15
11 26
5 13
13 11
24 28
26 18
17 12
1 28 27
23 3
16 11
4 7
14 27 4 16
0
42
6 18
15 35
10 36 23
4 40
37 10
26 14 18 38 11
29 42
35 6 4 8 13 30 2 29 1 15 28
8 35
39 18 4
9 18
33 6 26
19 42
24 4
12 39
18 40 34
31 21
16 33
22 3 15 4 12
13 4
42 5
7 18 23
27 8
20 38
36 1
17 5
40 14
21 3 27 35
3 6
34 36
41 39
32 41 27
5 8
14 1
23 11 19
2 28
25 14
0
44
15 11
36 19
43 25
21 32
26 21
1 19
7 23
32 29
17 6
35 41 42
11 43 26 2
20 12
30 40
28 26 10 25
24 30 37 10 43 5
39 14
42 41
3 10
25 11
41 43
23 8
12 9
4 17 25 22 39 10 38 3 15
10 7
18 21
40 23
27 9 13 7 29 14
9 41 10 4
37 19
34 44 3
44 19
19 6
16 39
29 28
38 35
14 11 27 6 5
2 33 27
13 16
31 34 42 40 41
0
25
4 21
25 3
7 20 17
18 1
13 6
23 6
1 9 13
2 24
10 1
12 22 11
3 17
17 24
19 1
5 14 23 11 16
21 4
8 24
24 25 7
16 21
6 19
20 6
11 9
14 2
15 3
0
45
34 7
10 18
21 45
7 43
31 40
32 29
25 27
19 28
3 27 1 29 11 18 23 15 10 38 42 43 31 45 2
29 45
28 7
37 5
36 14 41 22 23 31 8 26 9 30 19 21 38
38 17
13 44 22 25
5 11
30 4
8 3
33 7
4 35
14 8
2 43 7
20 38 36
1 10
24 2
15 39 43
18 24
27 38
40 27
35 21
44 11 12
16 3 39
39 20
9 11
6 22 15 21 25 20 13 17 35 5 26 9
0
36
16 7 30 31 13 27 3
25 26
26 30
5 10
27 22 13 7
34 16
22 24
17 28
15 6
11 19
24 27
14 36
6 19
23 30
32 23
36 14
35 26
20 29
1 31 21
33 6
10 15
3 19
19 35
7 9
29 4 16 9 36
21 29 30
18 36 7 4 21
28 1
2 8
13 4
12 24
30 26 3
4 24 12 18 15
31 33
8 15
0
37
26 16
35 32
24 37
33 5
21 30
7 27 20
12 9
28 33
9 15
8 37 6 3 34 22 27 2 4 29 36
19 30
3 16
27 29 9 18
31 37 29 24
36 16
18 37
14 22
30 31
16 28
20 12 17 27 16 2
10 4 34 28 19
6 5
2 13 34 9
17 16 13 26
4 31
5 32 26 28 13
15 4 2
1 22 31
13 26
22 9
23 37 34
37 34 20
34 2
29 1
11 20
32 30
25 10
0
30
12 29
15 24
2 16
19 28
21 8
22 28 6 19 4 27
27 2 22
14 12 28
9 1 18 8 27
1 3
30 10 7
13 21
10 12
25 7
8 4
4 27
18 6
17 11
5 3 14
29 7
11 15
7 29
26 8
23 30
3 27
20 14
16 13 2 19
6 14 8
24 22
0
12
8 7
2 9
10 6
6 11
12 10
11 9
3 4
4 2
7 4
5 7
9 10
1 12
0
21
11 15 3 21 14 17
14 13
10 2
8 14
18 11
4 17
6 13 3
17 18
19 21
16 12 17 15 7
5 9
21 3
12 9
13 10
9 16
2 21
3 8
7 1
1 18 16
20 13
0
6
4 6 3
2 1
3 1
6 1
1 5
0
33
27 30
29 21
7 25
18 4
32 29
24 17
8 17
12 23
23 16
19 6
5 11
10 6 19 28 21 14 2 27 29 9
20 24 27
9 2
2 19
14 23
15 6
16 18
17 5
3 33
30 9
28 3
4 17
22 10
33 6
13 20
6 2
25 32 19 5 9 8
31 21
1 15
26 23 28 15
0
28
19 8 12
11 24 6
20 24
13 9
26 23
14 5 17
24 8
22 25
1 20
4 26
6 12
10 20 19
12 1 19 18 27
18 8
16 12
3 17
15 2
8 4
2 5
9 26
7 22
17 25
27 14
23 3 5 9 27 21 18 8 28
0
27
7 2
20 8
25 2
3 21
15 1
16 27 7 20
5 21
2 22
23 17
6 14 16 9
18 10
12 16
26 3
4 19
17 18 2 8 16
22 21
1 13
9 2
10 27
24 20
8 15
13 21
14 24 20 6 13
21 8
11 23
19 9 22
0
13
10 3
3 13
5 3
1 8
9 6
4 1 13
13 8
11 3
12 1
7 10
8 1
2 9
6 5
0
42
1 29
19 27 9 20
34 14
29 42 17
41 5 40 2 29
7 20 2
40 18
10 21
16 36
14 29
20 25
27 15
22 29
11 5
31 23
39 38
24 41 14 29 42
12 37 38 24 17 35
35 40
13 17
5 36
8 30
23 18
33 7
38 32
28 36
36 1
9 8
18 14
30 15 12
21 3 28
15 5 25 18
32 42 8 26 25 1
4 16
25 32
26 6
0
11
6 7
11 5
2 5
5 11
10 6
7 4
4 1 6
9 10 5
1 3
8 2
0
25
19 16 13
13 12
22 23 16 6
14 22
24 20
16 10 6 7 5 15
10 13
1 20
2 17
20 21
18 22
8 24
15 10
9 3 5
17 25
7 21
23 1
25 20
12 4
3 8 9
6 8 9 12 4 23
5 23
21 23
4 17
11 3
0
27
10 4
21 23
13 22
3 25 9 16
16 2
18 6 14
24 25 27
26 17
17 22
11 21
14 13 19 24 20
25 13 19
8 16 26
6 15
2 23 21
5 27 12
1 20 12
7 20
15 9 21 6
22 7 20
12 21
9 18
4 1
0
10
5 1 6
9 3
4 3
7 4
6 9
10 7
8 1
1 3
3 10
2 4
0
5
2 5
5 1
4 3
1 4
0
41
30 3
15 24
23 37
39 25
9 39 22 38 34 29 18
18 20
35 14
6 34
40 19
16 27
31 5
11 29
1 40 32
4 33
17 11 16
36 7
21 23
27 28 21
10 34
34 37 19 3 27
3 5
25 15
8 10 16
20 37
28 7
19 1
5 35 2
2 27
12 7
33 31
26 25
38 40
29 33
7 2
32 41
24 15
13 4
0
37
15 10
1 11 29
26 9
10 37 25 34
35 32
6 23
33 31
30 22 32
19 20 35 25 5
23 8 31
4 21
2 16
22 21
32 30
3 27 32 19
5 16
11 14
16 18
14 13
24 18
8 29 1
12 6 18 28
29 17
36 11
7 2 11
13 21
37 28
34 21
31 14
21 5
20 11
25 5
17 29
9 6
0
45
14 34
6 17
43 41
27 40 37 5 13
8 29
9 41
19 14 42 35 5
30 5
3 31
13 44 3 9
40 14 2
10 43
35 11
18 16 37
17 45
34 33 43 31
16 21
4 6
31 4
99
90 34
75 42
92 95
37 50
80 84
52 29
43 84
6 69 24 47 14 37 59 95 86
69 74 96
21 14 70 1 3
51 71 73
59 13 84 79
7 63
79 42
12 79
40 46 12 60 94
41 85
96 31
34 90
32 97 99
1 20 69
15 61
71 95 35 46 94 37 83
58 54
87 51
14 1
46 39
93 97 9 16 54 71 85 5 84 24 95 59 87 70 72 15
53 76
45 46 71
89 58
74 35
22 27
18 63
8 96
64 9 49 61
26 73
36 74 92 54 38
30 94 29
24 58 52 84 96 88 5 70 83 10 66 94 81 56 48 18 80 61 42 26 29 7 21 39 34 1 90 2 85 51 28 95 4 76 41 49 93
23 70
35 30 61
13 15 10
70 38
33 70
28 83
68 81
47 93
95 81
88 14 48 16 75 7 5 55
78 5 87
65 38 29
72 23
17 5
16 7 6 87 76 46 68 61 63 21 50 85 25 1 37 4 13 48 56 11
48 78
81 11 6 63 95
31 6
9 8
86 75
61 6
5 23
39 34
2 46
99 66
25 63
73 56 69
66 47 53 80 6
3 42 22
10 59 65 11
94 95
63 66 97 57 30
49 43
44 98
82 58
20 32
62 67 72
56 37
4 9
60 69 66 42 8 20 82 7 21
27 15
54 52 78 49
84 12 62 88 57
42 20
38 19
50 66
29 88 98 60 19 17 37 78 59 16 85 65 72
57 61 12
83 15 54 53
11 31
77 85 63 23 25 14
67 9
98 46
19 8
76 15
97 41
91 37
0
0
Code: Select all
0
1
2
2
5
5
4
6
4
9
11
4
7
6
10
9
8
11
11
6
8
9
10
11
14
6
10
6
7
9
12
17
5
3
6
11
6
4
8
8
4
7
11
5
7
5
8
9
5
13
15
10
7
9
2
2
4
10
4
2
5
9
6
5
4
2
2
7
11
3
7
6
10
5
7
1
10
9
7
10
7
8
6
12
5
9
6
6
1
7
8
7
7
15
7
3
3
3
3
13
9
4
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
Re: 315 - Network
I solved it using tarjan's algorithm for finding articulation points, jakecho1's post is very helpful.