## 315 - Network

Moderator: Board moderators

Anupam Pathak
New poster
Posts: 7
Joined: Tue Jul 25, 2006 2:01 pm
Contact:

### Should root always articulation point?

Hello all,
I am trying to solve 315 by finding articulation points, but I stuck in a case where I am not sure root should be declare as articulation point even though it has more than two descendants. Is it always necessary to declare root as articulation point in this case. In fact, I think we are talking about graph not tree, so it is possible that descendants of the roots are connected at later levels.

Yours,
Anupam
Trying to reduce complexity of the World.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: Should root always articulation point?

Anupam Pathak wrote:Hello all,
I am trying to solve 315 by finding articulation points, but I stuck in a case where I am not sure root should be declare as articulation point even though it has more than two descendants. Is it always necessary to declare root as articulation point in this case. In fact, I think we are talking about graph not tree, so it is possible that descendants of the roots are connected at later levels.

Yours,
Anupam
Hmm.. To solve this problem, you would do DFS first..
Then you'll get directed acylic graph..
Now, you're going to take care of this DAG and the root node is where you started the DFS..
So, even though root node has many neighbors in original graph, it could have only one child in DAG..

Sorry if I misunderstood your question..

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### Re: 315 getting WA

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### Re: 315: Network

Dfs Visit always generate a tree or forest. As the graph is connected undirected it will produce a forest with only one tree. Then If the root has more then one children u must treat the root as articulation point.

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### Re: 315 Network

i cant figure out why WA.
anybody here to check my code?

Code: Select all

``````#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#define INF 1<<29
#define MAX 2000
#define WHITE 0
#define GRAY 1
#define BLACK 2

using namespace std;

/*****************Global varables *****************/

bool isInserted[MAX];
int color[MAX],dTime[MAX],fTime[MAX];
vector<int> V[MAX],AP;						          	/* AP for  Articulation points */
int prev[MAX],low[MAX];
int TimeValue = 0;

/**************** DFS Method *******************/

void callDfs(int u){
int i,v;
color[u] = GRAY;
dTime[u] = ++TimeValue;
low[u] = dTime[u];									/* For articilation point */
for(i = 0; i < V[u].size(); i++){
v = V[u].at(i);
if(color[v] == GRAY && v != prev[u]){
if(low[v] < low[u])
low[u] = low[v];							/* update low[u] cause low[v] always smaller then low[u] */
}
if(color[v] == WHITE){
prev[v] = u;
callDfs(v);

if(low[v] < low[u])
low[u] = low[v];

if(low[v] >= dTime[u] && !isInserted[u]){
if(AP.empty()){
AP.push_back(u);
isInserted[u] = true;
}
else if(AP.at(AP.size()-1) != u){
AP.push_back(u);
isInserted[u] = true;
}
}
}
}
color[u] = BLACK;
fTime[u] = ++TimeValue;
}

/**************** Flush Graph *****************************/

void graphFlush(int nVertex){
for(int i = 0; i<nVertex; i++)
while(!V[i].empty())
V[i].clear();
while(!AP.empty())
AP.clear();
}

/***************** PrintAP Articulation points *******/
void printAP(){
for(int i = 0; i< AP.size(); i++)
printf("%d ",AP.at(i)+1);
puts("");
}

/***************** IsRootAP Method ******************/
bool isRootAP(int root,int nVertex){
int c = 0,i;
for(i = 0; i<nVertex; i++){
if(prev[i] == root)
c++;
}
return (c != 1);
}

/***************** Set Low Method ********************/

void setLow(int nVertex){
for(int i = 0; i<nVertex; i++)
low[i] = INF;
}

/*************** Main Method ************************/
int main(){
//freopen("in.txt","rt",stdin);
int nVertex,in,out,i;
char str[1000],*p;

// scan the inputs
while(scanf("%d",&nVertex) == 1 && nVertex){
graphFlush(nVertex);

while(scanf("%d",&in) && in){
if(in == 0)
break;

gets(str);
p = strtok(str," ");

while(p){
out = atoi(p);
p = strtok(NULL," ");
V[in - 1].push_back(out - 1);               // For finding Articulation points make it undirected [u->v && v->u]
V[out - 1].push_back(in - 1);
}
}
// sort the vectors, lexographical priority
for(i = 0;i<nVertex; i++){
sort(V[i].begin(),V[i].end());
}

// initializing
memset(color,WHITE,sizeof(color));
memset(prev,-1,sizeof(prev));
memset(isInserted,false,sizeof(isInserted));
setLow(nVertex);

// call DFS
for(i = 0; i<nVertex; i++){
if(color[i] == WHITE){
callDfs(i);
}
}

if(!isRootAP(0,nVertex))
AP.pop_back();
printf("%d\n",AP.size());
}
return 0;
}``````

rifayat samee_du
New poster
Posts: 9
Joined: Tue Jul 11, 2006 8:44 am
Location: Beside you........

### Re: 315 Network

I think the given graph can be disconnected !!
My code handled that and got AC.

try this case :

Code: Select all

``````input:
7
1 2 3
2 3
5 6
6 7
0
0

output :
2

``````
Name : Sanzee
Location: In front of a x86 machine So...you never know may be beside you!!

nishith
New poster
Posts: 4
Joined: Wed Jul 07, 2010 11:17 pm

### Re: 315 Network

rifayat samee_du wrote:I think the given graph can be disconnected !!
My code handled that and got AC.

try this case :

Code: Select all

``````input:
7
1 2 3
2 3
5 6
6 7
0
0

output :
2

``````
I don't think so. My accepted code gives the output 1.
Because the the graph has two subgraph, in which only 6 is the articulation point. If anyone draw the graph, it will be cleared.

Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Contact:

### Re: 315 Network

nishith wrote-
rifayat samee_du wrote:I think the given graph can be disconnected !!
My code handled that and got AC.

try this case :

Code: Select all
input:
7
1 2 3
2 3
5 6
6 7
0
0

output :
2

I don't think so. My accepted code gives the output 1.
Because the the graph has two subgraph, in which only 6 is the articulation point. If anyone draw the graph, it will be cleared.
I think there is no input like this.I got Acc by providing output 0 and 7(number of vertex) both.So I think the graph is always connected.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359

hexflashor
New poster
Posts: 1
Joined: Mon May 14, 2012 10:45 am

### Re: 315 Network

The given graph is always connected, as given in the problem description.
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

afruizc
New poster
Posts: 15
Joined: Sat Oct 13, 2012 2:04 am

### Re: 315 Network

I have looked in everyones codes. I'm using Tarjan algorithm to find Articulation points. I had some problems representing the graph as an Adjacency List, so I changed it to a matrix, but still WA.
Here is my code:

Code: Select all

``````Cut after AC..
``````
I would really appreciate if some helps me out
Last edited by afruizc on Tue Jan 08, 2013 2:37 am, edited 1 time in total.

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

### Re: 315 Network

Code: Select all

``````//cut
``````
is it right ??? or the input is illegal as here graph isn't connected....???
Last edited by Mukit Chowdhury on Fri Nov 09, 2012 7:09 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

mkbs_cse09, try rewriting your input parsing to read a line at a time. Your code won't work with trailing whitespace on a line.

The graph should be connected, so that input is illegal.
Check input and AC output for thousands of problems on uDebug!

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

### Re: 315 Network

@Brianfry713.... I have edited my code,but still WA !!! would you check please now??

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<vector>
#define si 110
#define min(a,b) (a<b ?a:b)
using namespace std;
vector<long>ve[si];
char ch[110];
long l[si],df[si],rt[si],num;

void dfs(long node,long p)
{
l[node]=df[node]=num;
num++;
long ll=ve[node].size(),i,v;
for(i=0;i<ll;i++)
{
v=ve[node][i];
if(df[v]==0)
{
rt[node]++;
dfs(v,node);
l[node]=min(l[node],l[v]);
}
else if(v!=p)
l[node]=min(l[node],df[v]);
}
}

int main()
{
long n,u,v,i,ll,j,cnt;
while(~scanf("%ld",&n)&&n)
{
while(getchar()!='\n');
while(scanf("%ld",&u)&&u)
{
gets(ch);
ll=strlen(ch);
for(i=0;i<ll;i++)
{
if(ch[i]>=48&&ch[i]<=57)
{
v=0;
while(ch[i]>=48&&ch[i]<=57&&i<ll)
{
v=v*10+(ch[i]-48);
i++;
}
i--;
ve[u].push_back(v);
ve[v].push_back(u);
}
}
}
num=1;
dfs(1,-1);
cnt=0;
for(i=1;i<=n;i++)
{
ll=ve[i].size();
if(ll>1)
{
for(j=0;j<ll;j++)
{
v=ve[i][j];
if(l[v]>=df[i])
{
if(i==1&&rt[i]>1)   //to check the root,if root is also an articulation point
cnt++;
else if(i!=1)
cnt++;
break;
}
}
}
ve[i].clear();
}
printf("%ld\n",cnt);
for(i=1;i<=n;i++)
df[i]=l[i]=rt[i]=0;
}
return 0;
}
``````
for input,,,,

Code: Select all

``````5
1 2 3 4 5
0
5
1 2 3
2 3 4
4 5
0
5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
9
1 2 5 6
5 7 8
7 8
2 6
6 3 4
3 4
4 9
0
0
``````
My output is....

Code: Select all

``````1
2
1
2
4
``````
I need some critical input for my code....

brianfry713
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!

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

### Re: 315 Network

Why I've to run dfs N times ??? I am really disappointed... I've not found any problem yet now.... I was in confusion as I was sure you could give me some inputs for which my code would fail...but now what can I say !!!! Would you please tell me for what input my code fails,brianfry713 ????
I have learnt this algo during last 2 days.... It was my 1st problem of this algo... but now...
I have spent today fully for this problem...
May be you will understand my feelings...