Pagini recente » Cod sursa (job #2774288) | Cod sursa (job #1339922) | Cod sursa (job #2478580) | Cod sursa (job #2999013) | Cod sursa (job #440922)
Cod sursa(job #440922)
#include<fstream>
#include<vector>
using namespace std;
void read();
void doit();
void dfs( int x );
void write();
int n, m;
vector<vector<int> > mat(100005);
vector<bool> selected(100005);
int conex;
int main()
{
read();
doit();
write();
return 0;
}
void read()
{
ifstream fin( "dfs.in" );
fin >> n >> m;
for ( int i = 0; i < m; ++i )
{
int x, y;
fin >> x >> y;
mat[x].push_back(y);
mat[y].push_back(x);
}
fin.close();
}
void doit()
{
for ( int i = 1; i <= n; ++ i )
if ( !selected[i] )
{
dfs(i);
++conex;
}
}
void dfs( int x )
{
for ( vector<int>::iterator i = mat[x].begin(); i < mat[x].end(); ++i )
if ( !selected[*i] )
{
selected[*i] = true;
dfs(*i);
}
}
void write()
{
ofstream fout( "dfs.out" );
fout << conex;
fout.close();
}