#include<iostream.h>
#include<conio.h>
	int VIZITAT[20];
	int A[20][20];
	int V[20];
	int s;
//Numarul de varfuri ale graf. determina dimensiunea tablourilor
//A-matricea de  adiacenta
//V-vectorul de memorare a varf. nevizitate,vecine cu varful k
int URM[20];	//URM-retine nodul ce va trebui vizitat dupa nodul j
int n,m;	//n-numar varfuri; m-numar muchii
int p;		//p-indica primul element al stivei
int i,j;	//i,j-indici si contori
int k;		//k-varful in lucru
int x1,x2;	//x1 si x2 -varfurile ce determina o muchie
void INIT()
//initializarea matricei adiacenta si a vectorului VIZITAT
{
	for (i=1;i<=n;i++)
	{
		URM[i]=0;
		for (j=1;j<=n;j++) A[i][j]=0;
	}
}
void COMPLET()
//completarea matricei de adiacenta
{
	for (i=1;i<=m;i++)
	{
		cout<<" Muchia	"<<i<<" este ";
		cin>>x1;cout<<"      si ";cin>>x2;
		cout<<"sens: ";cin>>s;
		if(s!=2)
		{A[x1][x2]=s;A[x2][x1]=(-1)*s;}
		else
		{A[x1][x2]=1;A[x2][x1]=1;}
	};
}
void PRELUCRARE()
{			//se extrage primul varf din stiva
	j=V[p];
	k=URM[j]+1;
	//determina primul dintre vecinii k ai lui j, nevizitati inca
	while (k<=n&&(A[j][k]==0||(A[j][k]==1||A[j][k]==2)&&VIZITAT[k]==1)) k++;
	URM[j]=k;
	if (k==n+1) p=p-1;	//daca nu exista un asemenea k, se coboara in stiva
	else
	{
		//cout<<k<<" ";	
		VIZITAT[k]=1;	//se marcheaza varful k
		p=p+1;			//se trece pe nivelul urmator in stiva
		V[p]=k;			//se memoreaza varful k
	}
}
//Programul principal
int main()
{
	cout<<"\n"<<"Introduceti numarul de varfuri n: ";cin>>n;
	cout<<" Introduceti numarul de muchii m : "; cin>>m;
	INIT();
	COMPLET();
	cout<<" Varful de plecare: ";cin>>i;
	//prelucrarea  primului varf
	V[1]=i;		//introducere varf i in stiva V
	p=1;		//referire la primul element al listei
	VIZITAT[i]=1;	//se marcheaza varful i ca fiind vizitat
	//cout<<"    Plecand din varful "<<i<<", ";
	//cout<<"\n"<<" parcurgand graful prin metoda DF,";
	//cout<<"\n"<<" succesiunea varfurilor, este :";
	//cout<<"    "<<i<<" ";
	while (p>=1)	//cat timp stiva nu este vida, executa:
		PRELUCRARE();
	
    int ok;
	for(p=1;p<=n;p++)
	                 if(VIZITAT[p]==1) ok=1;
	                 else {ok=0;break;}
    if(ok) cout<<"\nGraf conex";
    else cout<<"\nMai multe componente conexe";
	getch();
}