315 - Network

[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

[helloneo]

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

[newton]

Answer must be 0

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

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

[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

[nishith]

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.

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

[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

[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

[Mukit Chowdhury]

Getting WA !!! Please Help !!!

Code: Select all

//cut

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

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

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

[brianfry713]

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

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