Page **3** of **5**

### Should root always articulation point?

Posted: **Fri Jun 08, 2007 3:07 pm**

by **Anupam Pathak**

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.

Please make me happy by giving answer of my question

Yours,

Anupam

### Re: Should root always articulation point?

Posted: **Fri Jun 08, 2007 6:12 pm**

by **helloneo**

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.

Please make me happy by giving answer of my question

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

### Re: 315 getting WA

Posted: **Wed Sep 24, 2008 8:58 pm**

by **newton**

Answer must be 0

### Re: 315: Network

Posted: **Wed Sep 24, 2008 9:06 pm**

by **newton**

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.

sorry for my bad english.

### Re: 315 Network

Posted: **Wed Sep 24, 2008 9:59 pm**

by **newton**

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

### Re: 315 Network

Posted: **Wed Apr 01, 2009 8:01 pm**

by **rifayat samee_du**

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

### Re: 315 Network

Posted: **Wed Aug 04, 2010 2:33 pm**

by **nishith**

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.

### Re: 315 Network

Posted: **Fri Sep 24, 2010 11:49 am**

by **sazzadcsedu**

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.

### Re: 315 Network

Posted: **Mon May 14, 2012 10:49 am**

by **hexflashor**

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

### Re: 315 Network

Posted: **Sat Oct 13, 2012 2:14 am**

by **afruizc**

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:

I would really appreciate if some helps me out

### Re: 315 Network

Posted: **Thu Nov 08, 2012 9:42 pm**

by **Mukit Chowdhury**

Getting WA !!! Please Help !!!

is it right ??? or the input is illegal as here graph isn't connected....???

### Re: 315 Network

Posted: **Thu Nov 08, 2012 10:37 pm**

by **brianfry713**

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.

### Re: 315 Network

Posted: **Fri Nov 09, 2012 7:11 am**

by **Mukit Chowdhury**

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

I need some critical input for my code....

### Re: 315 Network

Posted: **Fri Nov 09, 2012 8:47 pm**

by **brianfry713**

Try running dfs N times, once with each node turned off.

### Re: 315 Network

Posted: **Fri Nov 09, 2012 9:23 pm**

by **Mukit Chowdhury**

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