The problem is to finding a tree from a given graph.The main challenge is that the value of the node is not provided.
So adjacency matrix can not be used to solve the problem.
To define a tree for a directed graph : total edges = total vertices -1;root can not be more than one, each node must have one in coming edge (except root has 0),using dfs/bfs all the node can be traversed from root(each node has a unique path from tree.)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 |
#include <cstdio> #include <iostream> using namespace std; struct Node{ int number; Node *next; }; struct Edge{ int from,to; Edge(int f,int t); Edge *nextEdge; }; Node *nodeList=0; Edge *edgeList=0; int root; void init() { Node *p=nodeList,*q; while(p) { q=p; p=p->next; delete(q); } nodeList = new Node; nodeList->number=-100; nodeList->next=0; } int GetNodeIndex(int num) { Node *tmpNode=nodeList; int idx=0; while(tmpNode->next) { tmpNode = tmpNode->next; if(tmpNode->number==num) return idx; idx++; } tmpNode->next = new Node; tmpNode = tmpNode->next; tmpNode->number = num; tmpNode->next=0; return idx; } Edge::Edge(int a,int b) { int fr = GetNodeIndex(a); int t = GetNodeIndex(b); from = fr; to = t; } int CountNode() { Node *p=nodeList->next; int c=0; while(p) { p=p->next; c+=1; } return c; } int findIndegree(int nodeIndex) { Edge *p =edgeList; int cnt=0; while(p) { if(p->to==nodeIndex) cnt+=1; p=p->nextEdge; } return cnt; } void dfs(bool visited[],int nodeIdx) { visited[nodeIdx]=1; Edge *p=edgeList; while(p) { if(p->from==nodeIdx) dfs(visited,p->to); p=p->nextEdge; } } bool isTree() { int nodeCount = CountNode(); int tmp; root = -1; if(nodeCount==0)//empty tree return 1; //check for the root (=node having 0 indegree) and it is single in the graph //also check for the node have more than one parents for(int i=0;i<nodeCount;i++) { tmp = findIndegree(i); if(tmp>1) { return 0; } if(tmp==0) { if(root==-1) root=i; else { return 0; } } } if(root==-1) { return 0; } bool *visited= new bool[nodeCount]; for(int i=0;i<nodeCount;i++) visited[i]=false; dfs(visited,root); for(int i=0;i<nodeCount;i++) if(!visited[i]) { delete(visited); return 0; } delete(visited); return 1; } int main() { int from,to; int kase=1; while(scanf("%d%d",&from,&to),from>=0,to>=0) { init(); edgeList=0; while(from||to) { Edge *e = new Edge(from,to); e->nextEdge = edgeList; edgeList = e; scanf("%d%d",&from,&to); } printf("Case %d is %sa tree.\n",kase++,isTree()?"":"not "); while(edgeList) { Edge *dEdge=edgeList; edgeList=edgeList->nextEdge; delete(dEdge); } } return 0; } |