diff options
| author | Santo Cariotti <sancn@live.com> | 2017-03-17 21:00:23 +0100 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2017-03-17 21:00:23 +0100 |
| commit | eff9b7e3ac6f894e03d644bfba564909a260794c (patch) | |
| tree | 18772921408e1231f7f4f4088d875e22fe17b70c /Es 3.cpp | |
| parent | 47a54787726a158f89c4f0a0301cb2d80b55e267 (diff) | |
Grafi
Diffstat (limited to 'Es 3.cpp')
| -rw-r--r-- | Es 3.cpp | 109 |
1 files changed, 109 insertions, 0 deletions
diff --git a/Es 3.cpp b/Es 3.cpp new file mode 100644 index 0000000..d525f62 --- /dev/null +++ b/Es 3.cpp @@ -0,0 +1,109 @@ +#include <iostream>
+#define BIANCO 0 //Non Visitato
+#define NERO 2 //Visitato
+#define GRIGIO 1 //Non Finito
+#define INF 999999
+#include <vector>
+#include <fstream>
+#include <queue>
+#define MAXN 9999
+#define INDEF -1
+#include <stack>
+using namespace std;
+typedef pair <int,int> p;
+std::priority_queue<p, std::vector<p>, std::greater<p> > Q;
+int V,E;
+int matriceAdj[MAXN][MAXN];
+int T;
+struct nodo {
+ vector <int> adj;
+ int inizio,fine;
+}no[MAXN];
+ int colore[MAXN];
+ bool Ciclico=false;
+ bool dfsVisit (int u)
+ {
+ cout<<u<<endl;
+ colore[u]= GRIGIO;
+ int inizio=++T;
+ no[u].inizio=inizio;
+ int a;
+ for (int i=0;i<no[u].adj.size();i++)
+ {
+ a=no[u].adj[i];
+ if (colore[a]==GRIGIO)
+ {
+ Ciclico=true;
+ return 1;
+ }
+ if ( colore[a] == BIANCO )
+ {
+ int b=dfsVisit(a);
+ if (b)
+ {
+ return 1;
+ }
+ }
+ }
+ colore[u]= NERO;
+ int fine=++T;
+ no[u].fine=fine;
+ Q.push(p(fine,inizio));
+ return 0;
+ }
+
+ void dfsVisit2 (int u)
+ {
+ cout<<u<<endl;
+ colore[u]= GRIGIO;
+ int a;
+ for (int i=0;i<no[u].adj.size();i++)
+ {
+ a=no[u].adj[i];
+ if ( colore[a] == BIANCO )
+ dfsVisit(a);
+ }
+ colore[u]= NERO;
+ }
+ // Le chiamate ricorsive sono quanti sono i nodi GRIGI
+ void dfs()
+ {
+ for (int i=0;i<V;i++) colore[i]=BIANCO;
+ for (int i=0;i<V;i++) if (colore[i]==BIANCO) if (dfsVisit(i)) return;
+ }
+
+
+int main(int argc, char** argv) {
+ ifstream in ("input.txt");
+ ofstream out ("output.txt");
+ in>>V>>E;
+ int a,b;
+ for (int i=0;i<E;i++)
+ {
+ in>>a>>b;
+ no[a].adj.push_back(b);
+ }
+ dfs();
+ for (int i=0;i<V;i++)
+ {
+ cout<<"nodo "<<i<<endl;
+ cout<<"Inizio "<<no[i].inizio<<" Fine "<<no[i].fine<<endl;
+ }
+ if (!Ciclico)
+ {
+ for (int i=0;i<V;i++) colore[i]=BIANCO;
+ b=0;
+ while (!Q.empty())
+ {
+ a=Q.top().first;
+ Q.pop();
+ if (colore[a]==BIANCO)
+ {
+ dfsVisit2(a);
+ b++;
+ }
+ }
+ cout<<"Il numero di Componenti connesse e' "<<b;
+ }
+ return 0;
+}
|