Mai intai trebuie sa te autentifici.
Cod sursa(job #1410444)
Utilizator | Data | 31 martie 2015 02:03:27 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 85 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.03 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
class Node
{
public:
std::vector<int> neighbour;
};
std::vector<Node> nodes(100000);
std::vector<bool> visited(100000);
void dfs( int start )
{
std::list<int> queue;
queue.push_back( start );
while( !queue.empty() )
{
int head = queue.front();
queue.pop_front();
visited[head] = true;
for ( int i = 0; i < nodes[head].neighbour.size(); ++i )
{
if ( visited[nodes[head].neighbour[i]] == false )
{
queue.push_back( nodes[head].neighbour[i] );
}
}
}
}
int main( int argc, char* argv[] )
{
std::ifstream input( "dfs.in" );
std::ofstream output( "dfs.out" );
int N,M;
input >> N >> M;
for ( int i = 0; i < M; ++i )
{
int first, second;
input >> first >> second;
nodes[first].neighbour.push_back(second);
nodes[second].neighbour.push_back(first);
}
int contor = 0;
for ( int i = 1; i <= N; ++i )
{
if ( visited[i] == false )
{
dfs(i);
contor++;
}
}
output << contor;
input.close();
output.close();
return 0;
}