Pagini recente » Cod sursa (job #650576) | Cod sursa (job #1368579) | Cod sursa (job #2251847) | Cod sursa (job #1411701) | Cod sursa (job #815406)
Cod sursa(job #815406)
#include <fstream>
#include <vector>
#define MAX_N 100001
class Node
{
public:
int color;
std::vector<int> neighbours;
};
Node Graf[MAX_N];
void dfs(int _node, int _color)
{
Graf[_node].color = _color;
for (int i = 0; i < Graf[_node].neighbours.size(); ++ i)
if (Graf[Graf[_node].neighbours[i]].color == 0)
dfs(Graf[_node].neighbours[i], _color);
}
int main()
{
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
int N, M, x, y;
fin>>N>>M;
while(M--)
{
fin>>x>>y;
Graf[x].neighbours.push_back(y);
Graf[y].neighbours.push_back(x);
}
int color = 0;
for (x = N; x > 0; -- x)
{
if (Graf[x].color == 0)
dfs(x, ++ color);
}
fout<<color;
return 0;
}