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 !! :D
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 !! :D
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 !! :D
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:

Code: Select all

Cut after AC..
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 !!!

Code: Select all

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

Code: Select all

1
2
1
2
4
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... :(