Pagini recente » Cod sursa (job #774497) | Cod sursa (job #966139) | Cod sursa (job #80503) | Cod sursa (job #617656) | Cod sursa (job #938456)
Cod sursa(job #938456)
#include <iostream>
#include <fstream>
#include <vector>
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
struct vertex
{
int index;
vertex *next;
};
vertex *liste[100000];
int n, m, a[100][100], v[100000];
void citireMatrice()
{
int i, j;
fin>>n>>m;
while(fin>>i>>j)
{
a[i][j] = a[j][i] = 1;
}
}
void dfMatrice(int k)
{
for(int i = 1 ; i <= n ; i++)
{
if(a[i][k] == 1 && !v[i])
{
std::cout<<i<<" ";
v[i] = 1;
dfMatrice(i);
}
}
}
void bfMatrice(int k)
{
std::vector<int> vec;
vec.push_back(k);
while(vec.size())
{
for(int i = 1 ; i <= n ; i ++)
{
if(a[vec.front()][i] == 1 && !v[i])
{
a[vec.front()][i] = a[i][vec.front()] = 2;
std::cout<<i<<' ';
v[i] = 1;
vec.push_back(i);
}
}
vec.erase(vec.begin());
}
}
void citireListe()
{
int i, j;
fin>>n>>m;
while(fin>>i>>j)
{
vertex *newVex = new vertex;
newVex->index = j;
newVex->next = liste[i];
liste[i] = newVex;
vertex *newVex2 = new vertex;
newVex2->index = i;
newVex2->next = liste[j];
liste[j] = newVex2;
}
}
void dfListe(int k)
{
vertex *p = liste[k];
while(p)
{
if(!v[p->index])
{
//std::cout<<p->index<<" ";
v[p->index] = 1;
dfListe(p->index);
}
p = p->next;
}
delete p;
}
void bfListe(int k)
{
std::vector<int> vec;
vec.push_back(k);
while(vec.size())
{
vertex *p = liste[vec.front()];
while(p)
{
if(!v[p->index])
{
v[p->index] = 1;
vec.push_back(p->index);
std::cout<<p->index<<" ";
}
p = p->next;
}
delete p;
vec.erase(vec.begin());
}
}
int main()
{
/*
citireListe();
std::cout<<1<<" ";
v[1] = 1;
bfListe(1);*/
citireListe();
int nrTot = 0;
for(int i = 1; i <= n ; i++)
{
if(!v[i])
{
nrTot++;
dfListe(i);
}
}
std::cout<<nrTot;
/*
std::cout<<'\n'<<'\n';
for(int i = 1; i <= n ;i++)
{
std::cout<<i<<": ";
vertex *p = liste[i];
while(p)
{
std::cout<<p->index<<" ";
p = p->next;
}
delete p;
std::cout<<'\n';
}*/
//cout << "Hello world!" << '\n';
return 0;
}