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

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

Should root always articulation point?

Post by Anupam Pathak » Fri Jun 08, 2007 3:07 pm

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

Post by helloneo » Fri Jun 08, 2007 6:12 pm

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

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 315 getting WA

Post by newton » Wed Sep 24, 2008 8:58 pm

Answer must be 0

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 315: Network

Post by newton » Wed Sep 24, 2008 9:06 pm

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.

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 315 Network

Post by newton » Wed Sep 24, 2008 9:59 pm

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

Post by rifayat samee_du » Wed Apr 01, 2009 8:01 pm

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

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

Post by nishith » Wed Aug 04, 2010 2:33 pm

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.

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

Re: 315 Network

Post by sazzadcsedu » Fri Sep 24, 2010 11:49 am

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.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

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

Re: 315 Network

Post by hexflashor » Mon May 14, 2012 10:49 am

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

Post by afruizc » Sat Oct 13, 2012 2:14 am

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: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 315 Network

Post by Mukit Chowdhury » Thu Nov 08, 2012 9:42 pm

Getting WA !!! Please Help !!!

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

Post by brianfry713 » Thu Nov 08, 2012 10:37 pm

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: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 315 Network

Post by Mukit Chowdhury » Fri Nov 09, 2012 7:11 am

@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

Post by brianfry713 » Fri Nov 09, 2012 8:47 pm

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: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 315 Network

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

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

Post Reply

Return to “Volume 3 (300-399)”