Pagini recente » Cod sursa (job #2869205) | Cod sursa (job #2697931) | Cod sursa (job #1568238) | Cod sursa (job #1066431) | Cod sursa (job #475838)
Cod sursa(job #475838)
#include <fstream>
#include <vector>
using namespace std;
struct node
{
int value;
vector<node*> neighbors;
};
int n, m, i, x, y;
int sel[100001];
int compConex;
vector<node*> nodes;
void dfs( node* aNode );
int main()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
f >> n >> m;
for( i = 0; i < n; i++ )
{
node* newNode = new node;
newNode->value = i;
nodes.push_back( newNode );
}
for( i = 0; i < m; i++ )
{
f >> x >> y;
x--;
y--;
nodes[x]->neighbors.push_back( nodes[y] );
nodes[y]->neighbors.push_back( nodes[x] );
}
f.close();
for( i = 0; i < n; i++ )
{
if( !sel[i] )
{
compConex++;
dfs( nodes[i] );
}
}
g << compConex << "\n";
g.close();
return 0;
}
void dfs( node* aNode )
{
sel[aNode->value] = 1;
for( int ind = 0; ind < aNode->neighbors.size(); ind++ )
{
if( !sel[aNode->neighbors[ind]->value] )
{
dfs( aNode->neighbors[ind] );
}
}
}