equal
deleted
inserted
replaced
|
1 #include <iostream> |
|
2 #include <graph.h> |
|
3 #include <bfs.h> |
|
4 |
|
5 using namespace NEGRO; |
|
6 using namespace std; |
|
7 |
|
8 typedef Graph<int,int> TestGraph; |
|
9 |
|
10 int gcd(int a,int b) {int c; while((c=a%b)) {a=b;b=c;} ; return b;} |
|
11 |
|
12 int main() |
|
13 { |
|
14 TestGraph G; |
|
15 |
|
16 TestGraph::NodeIterator tn,n2; |
|
17 |
|
18 for(int i=1;i<=5000;i++) |
|
19 { |
|
20 *(tn=G.AddNode())=i; |
|
21 if(i==2) n2=tn; |
|
22 } |
|
23 |
|
24 for(TestGraph::NodeIterator n(G);n.isValid();++n) |
|
25 for(TestGraph::NodeIterator m(G);m.isValid();++m) |
|
26 if(gcd(*n,*m)>1) G.AddEdge(n,m); |
|
27 |
|
28 Bfs<default_bfs_T<TestGraph> > bfs; |
|
29 |
|
30 bfs.SetG(G); |
|
31 bfs.Init(n2); |
|
32 bfs.Run(); |
|
33 |
|
34 for(TestGraph::NodeIterator n(G);n.isValid();++n) |
|
35 cout << Get(bfs.tree_map,n).From() << "->" << Get(bfs.tree_map,n).To() |
|
36 << '\n'; |
|
37 |
|
38 } |