315 - Network

All about problems in Volume 3. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 315 Network

Post by Mukit Chowdhury » Fri Nov 09, 2012 9:25 pm

Even toolkit gives wrong output for this problem.... :(

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 315 Network

Post by @ce » Tue May 21, 2013 9:20 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 315 Network

Post by brianfry713 » Tue May 21, 2013 10:03 pm

brianfry713 wrote:Try running dfs N times, once with each node turned off.
Check input and AC output for thousands of problems on uDebug!

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 315 Network

Post by @ce » Wed May 22, 2013 4:35 am

@brianfry713...i got AC using brute force as u said.
brianfry713 wrote:Try running dfs N times, once with each node turned off.
But whys is the above algorithm not working...any help with that?
-@ce

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: 315 Network

Post by shuvokr » Sun Aug 25, 2013 9:43 pm

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

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 ..... 

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 315 Network

Post by brianfry713 » Tue Aug 27, 2013 2:40 am

Try running dfs N times, once with each node turned off.
Check input and AC output for thousands of problems on uDebug!

User avatar
sbaldrich
New poster
Posts: 3
Joined: Tue Aug 20, 2013 4:49 am

Re: 315 Network

Post by sbaldrich » Fri Sep 13, 2013 7:19 am

Just got AC. There are no disconnected graphs in the input as the problem statement says.
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.
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).

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

Re: 315 Network

Post by moxlotus » Sun Sep 15, 2013 11:37 am

brianfry713 wrote:Try running dfs N times, once with each node turned off.
Is that the only way of solving this problem? I am using tarjan's algorithm(iterative). but keep getting WA. :(
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.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 315 Network

Post by brianfry713 » Fri Sep 20, 2013 11:55 pm

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!

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

Re: 315 Network

Post by moxlotus » Fri Sep 27, 2013 8:15 am

BrianFry, thanks for the reply. found where my bug is. :D
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.

jakecho1
New poster
Posts: 2
Joined: Mon Feb 10, 2014 4:18 am

Re: 315: Network

Post by jakecho1 » Mon Feb 10, 2014 4:30 am

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:

Code: Select all

2
1 2 2 2
2 1
0
0
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.

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 315: Network

Post by vsha041 » Wed Apr 23, 2014 1:31 pm

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

Code: Select all

1
0
It should be

Code: Select all

1
0
0

ilo12
New poster
Posts: 1
Joined: Wed Dec 31, 2014 3:00 pm

Re: 315 - Network

Post by ilo12 » Wed Dec 31, 2014 3:04 pm

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;
}

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 315 - Network

Post by lighted » Wed Dec 31, 2014 3:57 pm

Input

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
Acc Output

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

bradd123
New poster
Posts: 17
Joined: Thu Jul 03, 2014 11:13 am

Re: 315 - Network

Post by bradd123 » Fri Jan 02, 2015 10:17 am

I solved it using tarjan's algorithm for finding articulation points, jakecho1's post is very helpful.

Post Reply

Return to “Volume 3 (300-399)”