MMM24's blog

poj is it a tree ? graph problem .
By MMM24, history, 10 years ago, In English

This the problem statement http://poj.org/problem?id=1308 The problem statement give a graph constructed by given each connected nodes and you have to determine if it's a tree or note

first and second are tree and the third is not .

My solution was to find first the root wich should be unique using set otherwise it's not a tree .

while(cin >> a >> b)
{
 graph[a][b]=1;
 s.insert(a);
 if(s.count(b)) s.erase(b);
}


 if(s.size()!=1)  cout << "Case "<<z<<" is not a tree." << endl  ;

once we have found the root i preform a dfs starting from the root .

dfs(root);
void dfs(int x)
{
    visit[x]++;
	if(visitv[x]>2)return;
	int i;
	for(i=0;i<1010;i++)if(graph[x][i])dfs(i);
}

each visited node will be incrimented by 1 . after dfs i check the number of times each node is visited , if it's visited more than one time than the given graph is not a tree otherwise it should be a tree . Any body can tell why this got a WA ? thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Just check 2 conditions 1) if the graph has cycles 2) if |v|!= |edges|-1 if any of the two condition is satisfied . graph is not a tree

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Using findSet and Union

→ Reply