Pagini recente » Cod sursa (job #2888841) | Cod sursa (job #2702112) | Cod sursa (job #1859459) | Cod sursa (job #2381938) | Cod sursa (job #505632)
Cod sursa(job #505632)
#include<fstream>
#include<vector>
#include<bitset>
#include<deque>
#include<list>
using namespace std;
ofstream fout("dfs.out");
void read();
void write();
void DF(int );
void ComponenteConexe();
void BF(int );
//void Push(int );
//void Pop(int );
int n, nr, m;
vector<vector<int> > a;
deque<int > Q;
bool s[100001];
/*
struct NOD
{
int x;
NOD *prim, *ultim;
};
*/
int main()
{
read();
ComponenteConexe();
fout << nr;
return 0;
}
void read()
{
ifstream fin("dfs.in");
int i, j;
fin >> n >> m;
a.resize(n+1);
while( fin >> i >> j)
{
a[i].push_back(j);
a[j].push_back(i);
}
fin.close();
}
void DF(int x)
{
int j;
s[x] = 1;
//fout << x << " ";
for(int i = 0; i < (int)a[x].size(); ++i)
{
j = a[x][i];
if(!s[j])
{
s[j] = 1;
DF(j);
// BF(j);
}
}
}
void ComponenteConexe()
{
for(int i = 1; i <= n; i++)
if( !s[i] )
{
nr++;
s[i] = 1;
// fout << "componenta nr " << nr << ": ";
DF(i);
// fout << endl;
}
}
void BF(int x)
{
s[x] = true;
Q.push_back(x);
fout << x << " ";
while( !Q.empty() )
{
for(int i = 0 ; i < (int)a[x].size(); ++i)
{
int j;
j = Q.front();
Q.pop_front();
if( !s[ a[x][i] ] )
{
Q.push_back(a[x][i]);
s [ a[x][i] ] = true;
fout << a[x][i] << " ";
}
}
}
}