Pagini recente » Cod sursa (job #1935801) | Cod sursa (job #898117) | Cod sursa (job #2442115) | Cod sursa (job #1899602) | Cod sursa (job #1464262)
#include <iostream>
#include <fstream>
#include <list>
#include <stack>
#include <vector>
#define MAX 200001
using namespace std;
typedef struct
{
int indice;
char culoare = 'N';
} nod;
void DFS(nod *nodgraf, list <nod> *graf)
{
stack <nod> stiva;
nodgraf->culoare = 'V';
stiva.push(*nodgraf);
while ( !stiva.empty() )
{
nod nodTop = stiva.top();
int vecin = -1;
std::list<nod>::iterator it;
for ( it = graf[nodTop.indice].begin() ; it != graf[nodTop.indice].end() ; ++it )
if ( it->culoare == 'N' )
{
vecin = it->indice;
it->culoare = 'V';
stiva.push(*it);
break;
}
if ( vecin == -1 )
stiva.pop();
}
}
int Complet(list <nod> *graf, int NrNoduri)
{
int i;
for ( i = 1 ; i <= NrNoduri ; i++ )
{
std::list<nod>::iterator it;
for ( it = graf[i].begin() ; it != graf[i].end() ; ++it )
if ( it->culoare == 'N' )
return 0;
}
return 1;
}
int CautaNodNeparcurs(list <nod> *graf, int NrNoduri)
{
int i;
for ( i = 1 ; i <= NrNoduri ; i++ )
{
std::list<nod>::iterator it;
for ( it = graf[i].begin() ; it != graf[i].end() ; ++it )
if ( it->culoare == 'N' )
return i;
}
return 1;
}
int ComponenteConexe(list <nod> *graf, int NrNoduri)
{
int compconexe = 0;
while ( !Complet(graf, NrNoduri) )
{
int n = CautaNodNeparcurs(graf, NrNoduri);
nod n1;
n1.indice = n;
DFS(&n1, graf);
compconexe++;
}
return compconexe;
}
int main()
{
ifstream input("dfs.in");
ofstream output("dfs.out");
int NrNoduri, NrMuchii, i;
/* Citire Date */
input >> NrNoduri >> NrMuchii ;
list <nod> graf[MAX];
nod nod1, nod2;
for ( i = 0 ; i < NrMuchii ; i++ )
{
input >> nod1.indice >> nod2.indice;
graf[nod1.indice].push_back(nod2);
graf[nod2.indice].push_back(nod1);
}
int cc = 0;
/* Afisare Graf */
for ( i = 1 ; i <= NrNoduri ; i++ )
{
/*
output << i ;
std::list<nod>::iterator it;
for ( it = graf[i].begin() ; it != graf[i].end() ; ++it )
output << "->" << it->indice << "," << it->culoare;
output << "\n";
*/
if ( graf[i].empty() )
cc++;
}
cc = cc + ComponenteConexe(graf, NrNoduri);
output << cc ;
return 0;
}